题解:拓扑排序的拓展应用
由拓扑排序可以得出一种排名方式,而要判断是否有多种排名方式时只需要在每个结点设置入度结点判定即可(由相同结点删去后导致入度为零的结点个数)。
code
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int head[5005],Next[N],to[N],cnt=1,into[5005],que[5005]; void build(){ int x,y; cin>>x>>y; Next[cnt]=head[x]; head[x]=cnt; to[cnt]=y; into[y]++; cnt++; } int main(){ int n,m,l=0,r=0; cin>>n>>m; for (int i=1;i<=m;i++) build(); int sum=0,bol=0; for (int i=1;i<=n;i++){ if (into[i]==0){ sum++; que[r++]=i; } if (sum>1) bol=1; } while (l<r){ sum=0; int cnt=que[l++]; for (int i=head[cnt];i>0;i=Next[i]){ if (--into[to[i]]==0){ sum++; que[r++]=to[i]; } if (sum>1) bol=1; } } for (int i=0;i<r;i++) printf("%d\n",que[i]); printf("%d\n",bol); return 0; }
标签:cnt,int,into,结点,Next,++,郁闷,记者,P1960 From: https://www.cnblogs.com/purple123/p/18090495