首页 > 代码库 > (简单) HDU 5154 Harry and Magical Computer，图论。
(简单) HDU 5154 Harry and Magical Computer，图论。
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;}
(简单) HDU 5154 Harry and Magical Computer，图论。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。