求强连通量，为1输出Yes否则No
Tarjan算法模板
具体讲解：https://www.byvoid.com/zht/blog/scc-tarjan
#include "stdio.h"#include "string.h"struct Edge{int v,next;}edge[100010];int head[10010],stack[10010],dfn[10010],low[10010];// stack栈； dfn深搜次序数组；low结点或者子树节点所能追溯到的最早栈中的标记数组int instack[10010];// 标记是否还在栈中int n,m,cnt,scnt,tot,top;void init(){cnt=0;scnt=top=tot=0; // 初始化连通分量标号，次序计数，栈顶指针memset(head,-1,sizeof(head));memset(dfn,0,sizeof(dfn)); // 结点搜索的次序编号数组}void add(int u,int v){edge[tot].v=v;edge[tot].next=head[u];head[u]=tot++;}void Tarjan(int w){int i,v,t;dfn[w]=low[w]=++tot;instack[w]=1;stack[top++]=w;for (i=head[w];i!=-1;i=edge[i].next){v=edge[i].v;if (dfn[v]==0){Tarjan(v);if (low[w]>low[v]) // 更新结点W所能到达的最小次数层low[w]=low[v];}elseif (instack[v] && dfn[v]<low[w])low[w]=dfn[v];}if (dfn[w]==low[w]) // 如果结点W是强连通分量的根{scnt++; // 连通分量标号+1do{t=stack[–top]; // 退栈instack[t]=0;}while (t!=w);}}void solve(){int i;for (i=1;i<=n;i++)if (dfn[i]==0)Tarjan(i);}int main(){int u,v;while (scanf("%d%d",&n,&m)!=EOF){if (n+m==0) break;init();while (m–){scanf("%d%d",&u,&v);add(u,v);}solve();if (scnt==1) printf("Yes\n");else printf("No\n");}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，你不勇敢，没人替你坚强！
