首页 > 代码库 > Best Coder Round#25 1001 依赖检测
Best Coder Round#25 1001 依赖检测
原题大致上就是检测一系列进程之间是否存在循环依赖的问题,形如: a->b->c->a, a->a ,都行成了循环依赖,事实上可以视为“检测链表中是否存在环”
AC代码:
#include <iostream>#include <set>#include <cstring>using namespace std;int main(){ int procs[10000]; int nProc, nDep; while( cin >> nProc >> nDep ) { memset(procs,0,10000); set<int> idSet; bool hasCircle = false; for( ; nDep>0; --nDep ) { int a, b; cin >> a >>b; idSet.insert(a); idSet.insert(b); if( a == b ) { hasCircle = true; } procs[a] = b; } if( !hasCircle ) { for( set<int>::iterator ii = idSet.begin(); ii != idSet.end(); ii++ ) { bool visit[10000] = {false}; int p = procs[*ii]; while( p && visit[p] == false ) { visit[p] = true; p = procs[p]; } if( p ) { hasCircle = true; break; } } } if( hasCircle ) { cout << "NO" << endl; }else{ cout << "YES" << endl; } } return 0;}
Best Coder Round#25 1001 依赖检测
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。