[GO] 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.

写真.png

――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

	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.

写真 (1).png

--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);
		}

	}

Recommended Posts

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.
I didn't know what to write in Maven's scope so I looked it up
[Action View :: Missing Template] I didn't understand the meaning of the error statement, so I looked it up.
I didn't understand the meaning of injection such as DI or @Autowired, so I looked it up.
I tried to solve the tribonacci sequence problem in Ruby, with recursion.
I don't really understand the difference between swift Error and NSError, so I tried to summarize it myself.
I tried to solve the tribonatch sequence problem in Ruby (time limit 10 minutes)
I tried to solve the problem of "multi-stage selection" with Ruby
I tried to sort the data in descending order, ascending order / Rails
I tried to solve the paiza campaign problem "Challenge from Kaito 813"
I tried to solve the problem of Google Tech Dev Guide
Memorandum: When I tried TensorFlow with Tribuo, it didn't work, so I went on a journey to find the head family and lost.
I tried to solve the past 10 questions that should be solved after registering with AtCoder in Java
I actually expressed the older sister problem in code and calculated it
Delegated type added in Rails 6.1 and Union types of GraphQL seem to be compatible, so I tried it
I tried to organize the session in Rails
[Beginner's point of view] I tried to solve the FizzBuzz problem "easily" with Ruby!
I want to morphologically analyze the log in the DB and put it in the DB to classify messages 1
I didn't understand the difference between Collections.emptyMap and Collections.EMPTY_MAP and my colleague got angry so I'll write it down here for self-discipline.
I tried to organize the cases used in programming
[Java] I tried to solve Paiza's B rank problem
Java classes and instances to understand in the figure
I tried to implement the Euclidean algorithm in Java
I finished watching The Rose of Versailles, so I tried to reproduce the ending song in Java
I tried to solve the Ruby karaoke machine problem (there is an example of the answer)
How to solve the problem when the value is not sent when the form is disabled in rails and sent
I tried to solve the Ruby bonus drink problem (there is an example of the answer)