Topological sort

by rishul matta

HTML

<div id="banner-message">
  <p>Hello World</p>
  <button>Change color</button>
</div>

CSS

body {
  background: #20262E;
  padding: 20px;
  font-family: Helvetica;
}

#banner-message {
  background: #fff;
  border-radius: 4px;
  padding: 20px;
  font-size: 25px;
  text-align: center;
  transition: all 0.2s;
  margin: 0 auto;
  width: 300px;
}

button {
  background: #0084ff;
  border: none;
  border-radius: 5px;
  padding: 8px 14px;
  font-size: 15px;
  color: #fff;
}

#banner-message.alt {
  background: #0084ff;
  color: #fff;
  margin-top: 40px;
  width: 200px;
}

#banner-message.alt button {
  background: #fff;
  color: #000;
}

JavaScript

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function(numCourses, prerequisites) {

  const adjacencyList = {};
  prerequisites.forEach(pre => {
    const [course, preCourse] = pre;
    if (adjacencyList[course] !== undefined) {
      adjacencyList[course].push(preCourse);
      return;
    }

    adjacencyList[course] = [preCourse];
  });

  const totalCourses = Array.from({
    length: numCourses
  }).map((a, index) => index);

  if (numCourses > totalCourses.length) {
    return [];
  }

  const possibleCourses = []
  const visited = {};
  let possible = true;

  const dfs = (node) => {
    if (!possible) {
      return
    }

    const neighbours = adjacencyList[node] || [];


    neighbours.forEach(neighbour => {
      if (visited[neighbour] === 'visiting') {
        possible = false;
        return;
      }

      if (!visited[neighbour]) {
        visited[neighbour] = 'visiting';
        dfs(neighbour);
      }

    });


    possibleCourses.push(node);
    visited[node] = 'done';
    return;

  };


  totalCourses.forEach(course => {
    if (!visited[course]) {
      dfs(course);
    }
  });


  if (possibleCourses.length >= numCourses && possible) {
    return possibleCourses.slice(0, numCourses);
  }

  return [];


};

findOrder(2, [
  [1, 0]
]);