<题目链接>
题目大意：
给你 0~n-1 这n个点，然后给出m个关系 ,u,v代表u->v的单向边，问你这m个关系中是否产生冲突。
解题分析：
不难发现，题目就是叫我们判断图中是否存在环，存在环，则说明冲突。所以我们对图进行拓扑排序，如果该图中所有的点均能在拓扑排序中成为入度为0的点，则说明不含环(因为环中的点不可能入度为0)。
#include <cstdio>
#include <cstring> #define rep(i,s,t) for(int i=s;i<t;i++)
const int N = ;
int g[N][N],ans[N][N],ind[N];
int n,m,num,cur,last;
bool toposort(){
cur=last=-,num=;
rep(k,,n){
rep(i,,n) if(!ind[i]){
cur=i;break;
}
if(cur==last)return false; //用last记录上一次入度为0的点，即如果cur经过一次循环查找后仍然等于last，说明图中已经不存在入度为0的点
++num;ind[cur]=-;
if(num==n)return true; //如果n个点均能依次在拓扑排序中成为入度为0的点，说明不存在环，即该图不产生冲突
rep(i,,n) if(g[cur][i]){
ind[i]--; //入度-1
}
last=cur; //更新last
}
return false;
}
int main(){
while(~scanf("%d%d",&n,&m),n||m){
memset(g,,sizeof(g));
memset(ind,,sizeof(ind));
rep(i,,m){
int u,v;scanf("%d%d",&u,&v);
if(!g[u][v]){ //防止重边
g[u][v]=;
ind[v]++;
}
}
toposort()?puts("YES"):puts("NO");
}
}
2018-11-20