本文共 1807 字，大约阅读时间需要 6 分钟。
Tarjan算法核心：
void dfs(int now,int v){ V[now] = low[now] = v; for(int i=pre[now];i!=0;i=E[i].pre){ if(V[E[i].to] == 0){ dfs(E[i].to,v+1); low[now] = min(low[now],low[E[i].to]); if(low[E[i].to] >= V[now]) sub[now]++; }else{ low[now] = min(low[now],V[E[i].to]); } }} 这题有个很蛋疼的地方，题目没有说明，输出一定要按节点序号。
第一次输出直接dfs搜索的，也省的统计了，果断WA掉。// ShellDawn// POJ1523// No.33#include#include #include #include #include #include #define MM(x,y) memset(x,y,sizeof(x))#define INF 0x3f3f3f3f#define LL long longusing namespace std;//#define maxn 1005int low[maxn]; // 能到达的最低层次int V[maxn]; // dfs层次int sub[maxn]; // 区块bool flag; // 是否有SPFstruct Edge{ int to; int pre;};Edge E[maxn*maxn];int pre[maxn];int cnt;void addE(int a,int b){ E[cnt].to = b; E[cnt].pre = pre[a]; pre[a] = cnt++; E[cnt].to = a; E[cnt].pre = pre[b]; pre[b] = cnt++;}void dfs(int now,int v){ V[now] = low[now] = v; for(int i=pre[now];i!=0;i=E[i].pre){ if(V[E[i].to] == 0){ dfs(E[i].to,v+1); low[now] = min(low[now],low[E[i].to]); if(low[E[i].to] >= V[now]) sub[now]++; }else{ low[now] = min(low[now],V[E[i].to]); } }}int main(){ //freopen("A.txt","r",stdin); int a,b; int T = 1; while(~scanf("%d",&a) && a){ if(T != 1) puts(""); printf("Network #%d\n",T++); cnt = 1; MM(pre,0); int N = 1; scanf("%d",&b); addE(a,b); N = max(N,a); N = max(N,b); while(~scanf("%d",&a) && a){ scanf("%d",&b); addE(a,b); N = max(N,a); N = max(N,b); } MM(V,0); MM(sub,0); MM(low,0); dfs(1,1); flag = false; if(sub[1] > 1){ flag = true; printf(" SPF node %d leaves %d subnets\n",1,sub[1]); } for(int i=2;i<=N;i++){ if(sub[i]!=0){ flag = true; printf(" SPF node %d leaves %d subnets\n",i,sub[i]+1); } } if(!flag) printf(" No SPF nodes\n"); } return 0;}
转载地址：http://snwji.baihongyu.com/