这是一道模版题
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define M 100010 void init(); void build(int u,int v); void solve(int n); void tarjan(int v); struct tt { int num,next; }edge[M]; int dfn[M],low[M],first[M],instack[M],stack[M],index,top,lin,sum; void init() { index=top=lin=sum=0; memset(dfn,0,sizeof(dfn)); memset(first,-1,sizeof(first)); } void build(int u,int v) { edge[lin].num=v; edge[lin].next=first[u]; first[u]=lin++; } void solve(int n) { int i; for(i=1;i<=n;i++) { if(dfn[i]==0) tarjan(i); } } void tarjan(int v) { int t,e; dfn[v]=low[v]=++index; instack[v]=1; stack[top++]=v; for(e=first[v];e!=-1;e=edge[e].next) { int j=edge[e].num; if(dfn[j]==0) { tarjan(j); if(low[v]>low[j])low[v]=low[j]; } else if(instack[j]==1&&dfn[j]<low[v]) { low[v]=dfn[j]; } } if(dfn[v]==low[v]) { sum++; do { t=stack[--top]; instack[t]=0; }while(t!=v); } } int main() { int n,m,i,a,b; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0)break; init(); for(i=0;i<m;i++) { scanf("%d%d",&a,&b); build(a,b); } solve(n); if(sum==1) printf("Yes "); else printf("No "); } return 0; }
/***************************************************************/
我参考的资料的顺序：
1：学长的ppt里的伪代码：
*tarjan(u)
*{
* DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值
* Stack.push(u) // 将节点u压入栈中
* for each (u, v) in E // 枚举每一条边
* if (v is not visted) // 如果节点v未被访问过
* tarjan(v) // 继续向下找
* Low[u] = min(Low[u], Low[v])
* else if (v in S) // 如果节点v还在栈内
* Low[u] = min(Low[u], DFN[v])
* if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根
* repeat
* v = S.pop // 将v退栈，为该强连通分量中一个顶点
* print v
* until (u== v)
*}
2：网上模版
#include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> using namespace std; #define MAXN 10010 #define MAXM 100010 struct Edge { int v, next; }edge[MAXM]; //边结点数组 int first[MAXN], stack[MAXN], DFN[MAXN], Low[MAXN], Belong[MAXM]; // first[]头结点数组,stack[]为栈,DFN[]为深搜次序数组， //Belong[]为每个结点所对应的强连通分量标号数组 // Low[u]为u结点或者u的子树结点所能追溯到的最早栈中结点的次序号 int instack[10010]; // instack[]为是否在栈中的标记数组 int n, m, cnt, scnt, top, tot; void init() { cnt = 0; scnt = top = tot = 0; //初始化连通分量标号，次序计数器，栈顶指针为0 memset(first, -1, sizeof(first)); memset(DFN, 0, sizeof(DFN)); //结点搜索的次序编号数组为0，同时可以当是否访问的数组使用 } void read_graph(int u, int v) //构建邻接表 { edge[tot].v = v; edge[tot].next = first[u]; first[u] = tot++; } void Tarjan(int v) //Tarjan算法求有向图的强连通分量 { int min, t; DFN[v] = Low[v] = ++cnt; //cnt为时间戳 instack[v] = 1; //标记在栈中 stack[top++] = v; //入栈 for(int e = first[v]; e != -1; e = edge[e].next) { //枚举v的每一条边 int j = edge[e].v; //v所邻接的边 if(!DFN[j]) { //未被访问 Tarjan(j); //继续向下找 if(Low[v] > Low[j]) Low[v] = Low[j]; // 更新结点v所能到达的最小次数层 } else if(instack[j] && DFN[j] < Low[v]) { //如果j结点在栈内, Low[v] = DFN[j]; } } if(DFN[v] == Low[v]) { //如果节点v是强连通分量的根 scnt++; //连通分量标号加1 do { t = stack[--top]; //退栈 instack[t] = 0; //标记不在栈中 Belong[t] = scnt; //出栈结点t属于cnt标号的强连通分量 }while(t != v); //直到将v从栈中退出 } } void solve() { for(int i = 1; i <= n; i++) //枚举每个结点，搜索连通分量 if(!DFN[i]) //未被访问 Tarjan(i); //则找i结点的连通分量 } int main() { while(scanf("%d%d",&n,&m) && (n || m)) { init(); while(m--) { int u, v; scanf("%d%d", &u, &v); read_graph(u, v); } solve(); //求强连通分量 if(scnt == 1) printf("Yes "); //只有一个强连通分量，说明此图各个结点都可达 else printf("No "); } return 0; }