Description
In reward of being yearly outstanding magic student, Harry gets a magical computer. When the computer begins to deal with a process, it will work until the ending of the processes. One day the computer got n processes to deal with. We number the processes from 1 to n. However there are some dependencies between some processes. When there exists a dependencies (a, b), it means process b must be finished before process a. By knowing all the m dependencies, Harry wants to know if the computer can finish all the n processes.
题目大致就是说对一个有向图判断是否有环。BC 25 的A题，这场比赛很幸运的爆零了，我觉得是因为A题不停的写错导致整个人都乱了，看来以后要注意，如果第一个题就乱了的话要注意调整，不能影响之后的发挥。
这个题目的题解是用的floyd写的，我使用dfs写的，貌似复杂度低一点。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; bool vis[105]; bool rem[105]; int n,m; int first[105]; int next[10005]; int bs[10005],be[10005]; bool dfs(int x) { int t=first[x]; while(t) { if(rem[be[t]]) //这里要注意先判断。 return 0; if(vis[be[t]]==0) { vis[be[t]]=1; rem[be[t]]=1; if(dfs(be[t])==0) return 0; rem[be[t]]=0; } t=next[t]; //不然会无限循环。 } return 1; } bool getans() { for(int i=1;i<=n;++i) if(vis[i]==0) { memset(rem,0,sizeof(rem)); //这里要注意清零。 rem[i]=1; vis[i]=1; if(dfs(i)==0) return 0; } return 1; } int main() { int a,b; int temp; while(~scanf("%d %d",&n,&m)) { memset(vis,0,sizeof(vis)); memset(first,0,sizeof(first)); memset(next,0,sizeof(next)); for(int i=1;i<=m;++i) { scanf("%d %d",&a,&b); bs[i]=b; be[i]=a; temp=first[b]; first[b]=i; next[i]=temp; } if(getans()) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }