[JAVA] Ich habe die topologische Sortierung nicht verstanden, also habe ich sie nachgeschlagen und in BFS implementiert und dann versucht, das AtCoder-Problem zu lösen.

Topologische Sortierung

Ich konnte es umsetzen, aber Wakatte Hainai

Was ist topologische Sortierung?

** Sortieren Sie so, dass jede gerichtete Seite eines gerichteten Graphen ohne geschlossenen Pfad in Vorwärtsrichtung liegt **

** Was ist Directed Non-Circuit Graph (DAG) **? DAG ist ein gerichteter Graph und ein Graph ohne geschlossenen Pfad. Dies wird manchmal verwendet, um die Prozedur einer Operation zu beschreiben. DAG kann topologisch sortieren.

Referenzseite

Topologische Sortierung Topologische Sortierungen durch dynamische Planung und Konstruktion von πDD zählen Einführung in die dynamische Planung Algorithmus und Datenstruktur

Die topologische Sortierung scheint eine Anordnung von Bäumen zu sein, wie in der folgenden Abbildung gezeigt.

• Es können mehrere Ergebnisse der topologischen Sortierung vorliegen (in der Abbildung sind 423651 und 426135 als Ergebnisse der topologischen Sortierung aufgeführt).

――Zum Beispiel ist der Baum 423615 in der obigen Abbildung in der folgenden Reihenfolge angeordnet.

1. Derjenige, der von nichts abhängt, ist ganz links (4)
2. Wenn die Adjazenzliste erstellt wird, ist die Wurzel diejenige, deren Eingabereihenfolge (sie scheint als Irijisu gelesen zu werden) 0 ist.
3. Als nächstes kommt derjenige, der nur von (4) (2) abhängt.
4. Durch Hinzufügen von (4) zur Liste für das Ergebnis und Löschen der Seite von (4) bis (2) wird die Eingabereihenfolge von (2) zu 0.
5. Das Löschen der Seite von (4) nach (2) bedeutet "Wenn Sie (4) zur Ergebnisliste hinzufügen, durchsuchen Sie die benachbarte Liste nach der Seite, die sich von (4) zu anderen Scheitelpunkten erstreckt, und dann Es bedeutet "abzüglich der Eingabereihenfolge des Verbindungsziels".
6. Als nächstes kommt derjenige, der nur von (2) (3 oder 6) abhängt.
7. Durch Hinzufügen von (2) zur Ergebnisliste und Löschen der Seiten von (2) bis (3) und (6) wird die Reihenfolge von (3) und (6) zu 0.
8. Als nächstes wird derjenige, der nur von (3) oder (6) ((6) abhängt, wenn (3) in [3] ausgewählt ist, (6) in [3] ausgewählt. Wenn dann, hängt es nur von (2) (3) ab (wie (6)) oder nur von (6) (1) oder (5))
9. Im Folgenden werden alle Abhängigkeiten überprüft

Versuchen Sie, mit BFS zu implementieren

• Nach der Implementierung können Sie dies auf der folgenden AOJ-Website überprüfen. GRL_4_B |Topologische Sortierung|Graph| Aizu Online Judge

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

		/*
		 *Adjazenzliste erstellen
		 */
		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);
		}
		//Ein Array zum Bestimmen, welche Reihenfolge 0 ist
		int indegree[] = new int[v];
		//Urteil der Bestellung 0
		for (int i = 0; i < v; i++) {
			List<Integer> temp = adj.get(i);
			//Knoten mit i ab
			for (int node : temp) {
				//Anzahl der eingehenden Bestellungen
				indegree[node]++;
			}
		}

		/*
		 *Warteschlange erstellen
		 *Packen Sie die Warteschlange mit der Reihenfolge 0
		 *Untersuchen Sie in der Größenordnung von 0
		 */
		ArrayDeque<Integer> q = new ArrayDeque<Integer>();
		for (int i = 0; i < v; i++) {
			if (indegree[i] == 0) {
				q.addLast(i);
			}
		}

		//Anzahl der besuchten Gipfel
		int cnt = 0;

		//Ergebnisse topologischer Art
		List<Integer> res = new ArrayList<Integer>();

		/*
		 * BFS
		 */
		while (!q.isEmpty()) {
			//Beginnen Sie mit der Suche nach dem Scheitelpunkt des Verbindungsziels
			int u = q.removeFirst();
			//Da die Reihenfolge 0 ist, addieren Sie zum Ergebnis
			res.add(u);

			/*
			 *Die Eingabereihenfolge des Verbindungsziels neben diesem Scheitelpunkt-Machen
			 *Als Ergebnis die Bestellung=Wenn es 0 wird, fügen Sie es dem Sortierergebnis hinzu und verwenden Sie es für die nächste Suche.
			 */
			for (int node : adj.get(u)) {

				indegree[node]--;
				if (indegree[node] == 0) {
					q.addFirst(node);
				}
			}
			cnt++;
			if (cnt > v) {
				System.out.println("In der Grafik ist Zirkulation");
				return;
			}
		}

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

Versuchen Sie, das AtCoder-Problem zu lösen

D - Restore the Tree

Lassen Sie uns das Problem der topologischen Sortierung herausfordern

Zusammenfassend wurde die Logik der topologischen Sortierung nahezu unverändert gelöst.

• Die Struktur von Eingabebeispiel 2 ist oben
• Die schwarze Seite ist die ursprüngliche Baumstruktur und die rote Seite ist die Seite, die später hinzugefügt wird.
• Die ursprüngliche Baumstruktur kann identifiziert werden, da beschrieben wird, dass "jeder andere Scheitelpunkt als die Wurzel eine gerichtete Seite hat, die sich von seinem übergeordneten Baum erstreckt".
• Wenn Sie nach topologischer Sortierung ordnen, ist der Scheitelpunkt, wenn Ihre Bestellung 0 wird (wenn Sie die Ihnen zugewandte Seite löschen), der Elternteil (ich verstehe den guten Wortlaut nicht ...)
• Wenn Sie beispielsweise eine Adjazenzliste erstellen, ist die Reihenfolge von (1) 3. -Es gibt eine Seite zu (1) in (4) (2) (6), aber wenn Sie eine topologische Sortierung durchführen, -Löschen Sie die Seite zu (1) in der Reihenfolge (4) (2) (6) -Wenn die Seite von (6) → (1) gelöscht wird, wird die Eingabereihenfolge zu (1) 0. -Wenn die Reihenfolge des Eintrags in (1) 0 wird, wird (6) Ihr eigenes Elternteil (wenn mehrere Eltern vorhanden sind, ist das von der Wurzel am weitesten entfernte Elternteil das Elternteil, wenn die ursprüngliche Baumstruktur vorhanden ist).

AtCoder: National Unified Programming King Finale (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("In der Grafik ist Zirkulation");
				return;
			}
		}

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

	}