首页 > 代码库 > 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 依赖检测