锐客网

  1. 首页 > it技术 > >

Codeforces Round #656 (Div. 3) E. Directing Edges （拓扑排序）

图论

【Codeforces Round #656 (Div. 3) E. Directing Edges （拓扑排序）】Codeforces Round #656 (Div. 3) E. Directing Edges （拓扑排序）
文章图片

题目链接
题目大意：题目大意：给你一个n个顶点m条边的图，其中一些边没有反向，其余边有方向，让你对每一条边赋一个方向，要求最终图不能形成自环。（没有重边）
思路：首先我以前不知道拓扑排序，也是通过这个题才知道的，一开始我的想法是并查集判环，但看到方向就不会了。看了别人题解才知道拓扑排序。
这里附上百度百科中的拓扑排序
这道题很明显如果本身有环肯定不行，这也是最容易想到的，那么就剩下给无向边定方向了。为了让新产生的有向边不形成环，要先进行一次拓扑排序，然后让拓扑序小的点指向拓扑序大的点，这样肯定不会形成环。为什么呢？
Codeforces Round #656 (Div. 3) E. Directing Edges （拓扑排序）
文章图片

好好理解这句话就明白了。

#include using namespace std; typedef long long ll; typedef unsigned long long ull; const int inf=0x3f3f3f3f; const int N=2e5+10; struct edge { int to,next; }e[N]; struct node { int u,v; node (int uu=0,int vv=0):u(uu),v(vv){} }; int head[N],cnt=0,deg[N],ans[N],num,n,m; vectorf; void addedge(int u,int v) { e[++cnt].to=v; e[cnt].next=head[u]; head[u]=cnt; } void bfs() { queueq; for(int i=1; i<=n; i++) if(deg[i]==0) q.push(i); while(!q.empty()) { int now=q.front(); q.pop(); num++; ans[now]=num; for(int i=head[now]; i; i=e[i].next) { int to=e[i].to; deg[to]--; if(deg[to]==0) q.push(to); } } } int main() { int t; scanf("%d",&t); while(t--) { f.clear(); memset(deg,0,sizeof(deg)); memset(ans,0,sizeof(ans)); memset(head,0,sizeof(head)); cnt=0; num=0; int o,x,y; scanf("%d%d",&n,&m); for(int i=1; i<=m; i++) { scanf("%d%d%d",&o,&x,&y); f.push_back(node(x,y)); if(o==1) { addedge(x,y); deg[y]++; } } bfs(); if(num!=n) printf("NO\n"); else { printf("YES\n"); for(int i=0; i<(int)f.size(); i++) { node now=f[i]; if(ans[now.u]

    推荐阅读


    上一篇：避免面试尴尬，你需要了解的20个架构师相关缩写

    下一篇：你还不打算试试Android|你还不打算试试Android X吗（）