C - Book 拓扑排序

谁践踏了优雅 2022-08-28 12:43 209阅读 0赞

[https://codeforces.com/contest/1573/problem/C][https_codeforces.com_contest_1573_problem_C]

判断还有度的节点一定放在最后  
注意更新的操作：如果比当前节点小，当前节点加一再比较，否则直接比较  
最后输出最大的操作次数就可以。

#include<bits/stdc++.h>
    using namespace std;
    const int N = 2e5 + 10;
    vector<int> to[N];
    int main() { 
    	ios::sync_with_stdio(false); cin.tie(0);
    	int t; cin >> t;
    	while (t--) { 
    		int n; cin >> n;
    		for (int i = 0; i < n; i++) to[i].clear();
    		
    		vector<int> in(n);
    		for (int i = 0; i < n; i++) { 
    			int x; cin >> x;
    			for (int j = 0; j < x; j++) { 
    				int k; cin >> k;
    				k--;
    				to[k].push_back(i); // 邻接表，存下一个节点
    				in[i]++;
    			}
    		}
    		queue<int> q;
    		vector<int> ts(n);
    		for (int i = 0; i < n; i++) { 
    			if (in[i] == 0) { 
    				q.push(i); // 存入度为0的点
    				ts[i] = 1;
    			}
    		}
    			
    			
    		while (!q.empty()) { 
    			int u = q.front(); q.pop();
    			for (auto v : to[u]) {   // 入度为0的下一个节点
    				in[v]--; // 入度减少一
    				if (v < u) ts[v] = max(ts[v], ts[u] + 1); 
    				// 如果 下一个更新的节点比当前节点小，当前节点要多更新一次，才会更新到下一个节点
    				else ts[v] = max(ts[v], ts[u]);
    				// 待更新的节点 比 当前节点大，那么只需要比较跟新的次数
    				if (!in[v])q.push(v); 
    			}
    		}
    		int ok = 1;
    		for(int i = 0; i < n; i++)
    			if(in[i]) { ok = 0; break;}
    		if(!ok) {  cout << "-1\n"; continue; }
    		cout << *max_element(ts.begin(),ts.end()) << '\n';
    		
    	}
    	
    }

[https_codeforces.com_contest_1573_problem_C]: https://codeforces.com/contest/1573/problem/C

发表评论取消回复

表情：

评论列表（有 0 条评论，209人围观）

还没有评论，来说两句吧...

相关阅读

相关拓扑排序以及拓扑排序算法

拓扑排序对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈

小咪咪/ 2023年09月28日 22:58/ 0 赞/ 27 阅读

相关 c语言拓扑排序界面_C和C ++中的拓扑排序

![da779e4a3ad6a2dc782747c884352980.png][] c语言拓扑排序界面 Here you will learn and get progra

桃扇骨/ 2022年12月07日 13:56/ 0 赞/ 171 阅读

相关拓扑排序（C语言）

在一个有向无环图中，用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网，简称AOV-网。对AOV-网，可用拓扑排序来得到他们顶点数据的优先关系，即拓

旧城等待，/ 2022年10月14日 13:54/ 0 赞/ 209 阅读

相关 C - Book 拓扑排序

[https://codeforces.com/contest/1573/problem/C][https_codeforces.com_contest_1573_proble

谁践踏了优雅/ 2022年08月28日 12:43/ 0 赞/ 210 阅读

相关 C++ 拓扑排序算法

拓扑排序有向无环图如果一个有向图的任意顶点都无法通过一些有向边回到自身，那么称这个有向图为有向无环图。拓扑排序拓扑排序是将有向无环图G的

缺乏、安全感/ 2022年06月10日 11:50/ 0 赞/ 208 阅读

相关拓扑排序

什么是拓扑排序? 在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序

冷不防/ 2022年06月09日 05:57/ 0 赞/ 248 阅读

相关拓扑排序

拓扑排序一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就

小鱼儿/ 2022年04月10日 08:23/ 0 赞/ 270 阅读

相关拓扑排序

（1）有向无环图无环的有向图，简称 DAG (Directed Acycline Graph) 图。有向无环图在工程计划和管理方面的应用：除最简单的情况之外，几

古城微笑少年丶/ 2022年03月18日 12:35/ 0 赞/ 317 阅读

相关拓扑排序

拓扑排序：拓扑排序是根据离散数学中有关偏序与全序定义的。 ![0_1314168765l7fq.gif][] 若一个集合 X 上的关系 R 是自反的反

淩亂°似流年/ 2021年12月23日 02:43/ 0 赞/ 373 阅读

相关拓扑排序

一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程

野性酷女/ 2021年09月19日 05:04/ 0 赞/ 489 阅读