[JAVA] I didn't understand the topological sort, so I looked it up and implemented it in BFS, and then tried to solve the AtCoder problem.

Topological sort

I was able to implement it, but Wakatte Hainai

What is Topological Sort?

** Sort so that each directed edge of a directed graph without a cycle is in the forward direction **

** What is Directed Acyclic Graph (DAG) **? A DAG is a directed graph and a graph without a cycle. This is sometimes used to describe the procedure of an operation. DAGs can do topological sort.

Reference site

Topological Sort Enumeration of topological sort by dynamic programming and construction of πDD Introduction to Dynamic Programming Algorithm and data structure

Topological sort seems to be a sort of trees arranged in order as shown in the figure below.

• There may be multiple results of topological sort (in the figure, 423651 and 426135 are listed as the results of topological sort).

――For example, the tree 423615 in the above figure is arranged in the following order.

1. The one that does not depend on anything is the leftmost (4)
2. At the stage of creating the adjacency list, the one with 0 degree (it seems to be read as Irijisu) is the root
3. Next is the one that depends only on (4) (2)
4. As a result of adding (4) to the list for the result and deleting the edges from (4) to (2), the degree of input of (2) becomes 0.
5. Deleting the edge from (4) to (2) means, "When adding (4) to the result list, search the adjacent list for the edge extending from (4) to another vertex, and then It means "minus the input degree of the connection destination".
6. Next is the one that depends only on (2) (3 or 6)
7. As a result of adding (2) to the list for the result and deleting the edges from (2) to (3) and (6), the degree of input of (3) and (6) becomes 0.
8. Next, the one that depends only on (3) or (6) ((6) if (3) is selected in [3], (6) is selected in [3] If then, it depends only on (2) (3) (same as (6)) or only on (6) (1) or (5))
9. Below, we will check all the dependencies

Try to implement with BFS

• Once implemented, you can check it on the AOJ site below. GRL_4_B |Topological sort|Graph| Aizu Online Judge

	private void solveA2() {
		int v = nextInt();
		int e = nextInt();

		/*
		 *Create adjacency list
		 */
		List<List<Integer>> adj = new ArrayList<List<Integer>>();
		for (int i = 0; i < v; i++) {
			adj.add(new ArrayList<Integer>());
		}

		for (int i = 0; i < e; i++) {
			int from = nextInt();
			int to = nextInt();
			adj.get(from).add(to);
		}
		//Array for determining those with an input degree of 0
		int indegree[] = new int[v];
		//Judge 0 degree
		for (int i = 0; i < v; i++) {
			List<Integer> temp = adj.get(i);
			//Nodes with i as from
			for (int node : temp) {
				//Number of degrees
				indegree[node]++;
			}
		}

		/*
		 *Create queue
		 *Queues with 0 degrees
		 *Investigate from 0 degrees
		 */
		ArrayDeque<Integer> q = new ArrayDeque<Integer>();
		for (int i = 0; i < v; i++) {
			if (indegree[i] == 0) {
				q.addLast(i);
			}
		}

		//Number of vertices visited
		int cnt = 0;

		//Topological sort results
		List<Integer> res = new ArrayList<Integer>();

		/*
		 * BFS
		 */
		while (!q.isEmpty()) {
			//Start searching for the vertex to connect to
			int u = q.removeFirst();
			//Since the degree is 0, add to the result
			res.add(u);

			/*
			 *Degree of the next connection destination of this vertex-To do
			 *As a result, the degree of entry=If it becomes 0, add it to the sort result and use it for the next search.
			 */
			for (int node : adj.get(u)) {

				indegree[node]--;
				if (indegree[node] == 0) {
					q.addFirst(node);
				}
			}
			cnt++;
			if (cnt > v) {
				System.out.println("There is circulation in the graph");
				return;
			}
		}

		for (int i : res) {
			out.println(i);
		}
	}

Try to solve the AtCoder problem

D - Restore the Tree

Let's challenge the problem of using topological sort

In conclusion, the logic of topological sort was solved with almost no modification.

--The structure of input example 2 is above --The black side is the original tree structure, and the red side is the side added later. --The original tree structure can be identified because there is a description that "each vertex other than the root has one directed side extending from its parent". --When arranging by topological sort, the vertex when your degree is 0 (when you delete the side facing you) is the parent (I don't understand the good wording ...) --For example, when you create an adjacency list, the degree of entry in (1) is 3. -There are edges to (1) in (4) (2) (6), but if you sort topologically, -Delete the edge to (1) in the order of (4) (2) (6) -When the side of (6) → (1) is deleted, the degree of input to (1) becomes 0. -When the degree to (1) becomes 0, (6) becomes your parent (when there are multiple parents, the parent farthest from the root is the parent when the original tree structure)

AtCoder: National Unified Programming King Qualifying (D --Restore the Tree)

	private void solveA() {
		int v = nextInt();
		int e = nextInt();

		List<List<Integer>> rinsetuList = new ArrayList<List<Integer>>();

		for (int i = 0; i < v; i++) {
			rinsetuList.add(new ArrayList<Integer>());
		}

		int[] indegrees = new int[v];
		for (int i = 0; i < v - 1 + e; i++) {
			int from = nextInt() - 1;
			int to = nextInt() - 1;
			rinsetuList.get(from).add(to);
			indegrees[to]++;
		}

		ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
		for (int i = 0; i < indegrees.length; i++) {
			if (indegrees[i] == 0) {
				queue.addLast(i);
			}
		}

		int[] par = new int[v];
		int cnt = 0;
		while (queue.size() != 0) {
			int index = queue.removeLast();

			for (Integer nextDegree : rinsetuList.get(index)) {
				int nextCnt = --indegrees[nextDegree];
				if (nextCnt == 0) {
					queue.addLast(nextDegree);
					par[nextDegree] = index + 1;
				}
			}
			if (cnt > v) {
				out.println("There is circulation in the graph");
				return;
			}
		}

		for (int i : par) {
			out.println(i);
		}

	}