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[];
bool rem[];
int n,m;
int first[];
int next[];
int bs[],be[]; bool dfs(int x)
{
int t=first[x]; while(t)
{
if(rem[be[t]]) //这里要注意先判断。
return ; if(vis[be[t]]==)
{
vis[be[t]]=;
rem[be[t]]=; if(dfs(be[t])==)
return ;
rem[be[t]]=;
} t=next[t]; //不然会无限循环。
} return ;
} bool getans()
{
for(int i=;i<=n;++i)
if(vis[i]==)
{
memset(rem,,sizeof(rem)); //这里要注意清零。
rem[i]=;
vis[i]=;
if(dfs(i)==)
return ;
} return ;
} int main()
{
int a,b;
int temp; while(~scanf("%d %d",&n,&m))
{
memset(vis,,sizeof(vis));
memset(first,,sizeof(first));
memset(next,,sizeof(next)); for(int i=;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 ;
}