[JAVA] Je ne comprenais pas le tri topologique, alors je l'ai recherché et mis en œuvre dans BFS, puis j'ai essayé de résoudre le problème d'AtCoder.

Tri topologique

J'ai pu l'implémenter, mais Wakatte Hainai

Qu'est-ce que le tri topologique?

** Trier de manière à ce que chaque côté dirigé d'un graphe orienté sans chemin fermé soit dans le sens avant **

** Qu'est-ce qu'un graphique non-tour dirigé (DAG) **? DAG est un graphe orienté et un graphe sans chemin fermé. Ceci est parfois utilisé pour décrire la procédure d'une opération. Le DAG peut effectuer un tri topologique.

Site de référence

Tri topologique Comptage des sortes topologiques et construction de πDD par planification dynamique Introduction à la planification dynamique Algorithme et structure des données

Le tri topologique semble être un arrangement d'arbres comme le montre la figure ci-dessous.

• Il peut y avoir plusieurs résultats de tri topologique (dans la figure, 423651 et 426135 sont répertoriés comme les résultats du tri topologique).

――Par exemple, l'arborescence 423615 de la figure ci-dessus est disposée dans l'ordre suivant.

1. Celui qui ne dépend de rien est le plus à gauche (4)
2. Lorsque la liste de contiguïté est créée, la racine est celle dont l'ordre d'entrée (il semble être lu comme Irijisu) est 0.
3. Vient ensuite celui qui ne dépend que de (4) (2)
4. Suite à l'ajout de (4) à la liste du résultat et à la suppression du côté de (4) à (2), l'ordre d'entrée de (2) devient 0.
5. La suppression du côté de (4) à (2) signifie: «Lors de l'ajout de (4) à la liste de résultats, recherchez dans la liste adjacente le côté s'étendant de (4) à d'autres sommets, puis recherchez le côté suivant. Cela signifie "moins l'ordre d'entrée de la destination de connexion".
6. Vient ensuite celui qui ne dépend que de (2) (3 ou 6)
7. Suite à l'ajout de (2) à la liste des résultats et à la suppression des côtés de (2) à (3) et (6), l'ordre de (3) et (6) devient 0.
8. Ensuite, celui qui ne dépend que de (3) ou (6) ((6) si (3) est sélectionné dans [3], (6) est sélectionné dans [3] Si alors, cela ne dépend que de (2) (3) (identique à (6)) ou uniquement de (6) (1) ou (5))
9. Ci-dessous, nous vérifierons toutes les dépendances

Essayez de mettre en œuvre avec BFS

• Une fois implémenté, vous pouvez le vérifier sur le site AOJ ci-dessous. GRL_4_B |Tri topologique|Graphique| Aizu Online Judge

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

		/*
		 *Créer une liste de contiguïté
		 */
		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);
		}
		//Un tableau pour déterminer quel ordre est 0
		int indegree[] = new int[v];
		//Jugement d'ordre 0
		for (int i = 0; i < v; i++) {
			List<Integer> temp = adj.get(i);
			//Nœuds avec i à partir de
			for (int node : temp) {
				//Nombre de commandes entrantes
				indegree[node]++;
			}
		}

		/*
		 *Créer une file d'attente
		 *Emballez la file d'attente avec 0 commande
		 *Rechercher à partir de l'ordre de 0
		 */
		ArrayDeque<Integer> q = new ArrayDeque<Integer>();
		for (int i = 0; i < v; i++) {
			if (indegree[i] == 0) {
				q.addLast(i);
			}
		}

		//Nombre de pics visités
		int cnt = 0;

		//Résultats du tri topologique
		List<Integer> res = new ArrayList<Integer>();

		/*
		 * BFS
		 */
		while (!q.isEmpty()) {
			//Commencez à rechercher le sommet de destination de la connexion
			int u = q.removeFirst();
			//Puisque l'ordre est 0, ajoutez au résultat
			res.add(u);

			/*
			 *L'ordre d'entrée de la destination de connexion à côté de ce sommet-Faire
			 *En conséquence, la commande=S'il devient 0, ajoutez-le au résultat du tri et utilisez-le pour la recherche suivante.
			 */
			for (int node : adj.get(u)) {

				indegree[node]--;
				if (indegree[node] == 0) {
					q.addFirst(node);
				}
			}
			cnt++;
			if (cnt > v) {
				System.out.println("Il y a circulation dans le graphique");
				return;
			}
		}

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

Essayez de résoudre le problème d'AtCoder

D - Restore the Tree

Remettons en question le problème de l'utilisation du tri topologique

En conclusion, la logique du tri topologique a été résolue avec presque aucune modification.

--La structure de l'exemple d'entrée 2 est ci-dessus

• Le côté noir est la structure arborescente d'origine et le côté rouge est le côté ajouté plus tard.
• La structure arborescente d'origine peut être identifiée car il existe une description selon laquelle "chaque sommet autre que la racine a un côté dirigé s'étendant depuis son parent". --Lors de l'organisation dans un tri topologique, le sommet lorsque votre ordre d'entrée devient 0 (lorsque vous supprimez le côté qui vous fait face) est le parent (je ne comprends pas le bon libellé ...)
• Par exemple, lorsque vous créez une liste de contiguïté, l'ordre de (1) est 3. -Il y a un côté à (1) dans (4) (2) (6), mais si vous faites un tri topologique, -Supprimer le côté de (1) dans l'ordre de (4) (2) (6) -Lorsque le côté de (6) → (1) est supprimé, l'ordre d'entrée de (1) devient 0. -Lorsque l'ordre d'entrée de (1) devient 0, (6) devient votre propre parent (lorsqu'il y a plusieurs parents, le parent le plus éloigné de la racine est le parent lorsque l'arborescence d'origine)

AtCoder: National Unified Programming King Finals (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("Il y a circulation dans le graphique");
				return;
			}
		}

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

	}