传送门:
解题思路:
如果整个图只有一个连通分量输出“Yes”,其它就输出“NO”
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 9 const int MAXN=100010;10 const int MAXM=2000010;11 12 struct Edge{13 int to,next;14 }edges[MAXM];15 int head[MAXN],tot;16 17 void init(){18 memset(head,-1,sizeof(head));19 tot=0;20 }21 22 void addEdge(int u,int v){23 edges[tot].to=v;24 edges[tot].next=head[u];25 head[u]=tot++;26 }27 28 int DFN[MAXN],LOW[MAXN],Belong[MAXN],Stack[MAXN];29 int Index,top;30 int scc;31 bool Instack[MAXN];32 int num[MAXN];33 34 void Tarjan(int u){35 int v;36 LOW[u]=DFN[u]=++Index;37 Stack[top++]=u;38 Instack[u]=true;39 40 for(int i=head[u];i!=-1;i=edges[i].next){41 v=edges[i].to;42 43 if(!DFN[v]){44 Tarjan(v);45 if(LOW[u]>LOW[v]) LOW[u]=LOW[v];46 }else if(Instack[v]&&LOW[u]>DFN[v])47 LOW[u]=DFN[v];48 }49 50 if(LOW[u]==DFN[u]){51 scc++;52 53 do{54 v=Stack[--top];55 Instack[v]=false;56 num[scc]++;57 Belong[v]=scc;58 }while(v!=u);59 }60 }61 62 void solve(int N){63 memset(DFN,0,sizeof(DFN));64 memset(Instack,false,sizeof(Instack));65 memset(num,0,sizeof(num));66 67 Index=top=scc=0;68 69 for(int i=1;i<=N;i++){70 if(!DFN[i])71 Tarjan(i);72 }73 74 if(scc>1)75 cout<<"No"<