結(jié)合tarjan算法思想，這題終于寫了出來。

同樣用dfs將圖變成為一顆樹，這樣可以提供許多有用的性質(zhì)。

對于一個無向連通圖，dfs后的樹為只有回邊（回邊Euv,v是u的祖先）和生成樹的邊的圖。 那么在遍歷到一個點u的時候，可以知道如果不考慮這個點，如果與u相鄰的點連通那么u不是割點，否則是割點。 那么只需要判斷與u相鄰的點是否連通就行了，于是借鑒tarjan求強(qiáng)連通的辦法，在dfs時，對每個點標(biāo)記一個深度low[N]也就是從根到這個點最短路徑（經(jīng)過的最小結(jié)點數(shù)）， 然后在遍歷到u點的時候，看看與u相鄰的點v的low[v], 如果low[U] >= low[u]那么說明u就是割點. ?因為v點無法到達(dá)u相鄰的某些點。 當(dāng)然當(dāng)u為根節(jié)點的時候要特判

?

1 2
5 4
3 1
3 2
3 4
3 5
01 2
2 3
3 4
4 5
5 1
01 2
2 3
3 4
4 6
6 3
2 5
5 1
00

Network #1SPF node 3 leaves 2 subnetsNetwork #2No SPF nodesNetwork #3SPF node 2 leaves 2 subnetsSPF node 3 leaves 2 subnets

?

// start time 12:44
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define N 1010
#define INF 0x3ffffff
int g[N][N];
int mark[N];
int low[N];
int save[N];
int n;void dfs(int s,int cnt)
{low[s]=cnt;int mi=INF;int k=0;for(int i=1;i<=n;i++){if(g[s][i]==0||s==i) continue;if(low[i] == -1){dfs(i,cnt+1);if( low[i] >= cnt ) k++;}mi=min(low[i],mi);}low[s]=mi;if(cnt==0) k--;if(k!=0) save[s]=k;
}int main()
{int tt=1;int x,y;while(scanf("%d",&x)&&x){memset(mark,0,sizeof(mark));mark[x]=1;n=0;if(x>n) n=x;memset(g,0,sizeof(g));memset(save,-1,sizeof(save));memset(low,-1,sizeof(low));scanf("%d",&y);mark[y]=1;if(y>n) n=y;g[x][y]=g[y][x]=1;while(scanf("%d",&x)&&x){mark[x]=1;if(x>n) n=x;scanf("%d",&y);mark[y]=1;if(y>n) n=y;g[x][y]=g[y][x]=1;}for(int i=1;i<=n;i++)if(mark[i]==1){dfs(i,0);break;}printf("Network #%d\n",tt++);int flag=0;for(int i=1;i<=n;i++){if(save[i]!=-1){flag=1;printf("  SPF node %d leaves %d subnets\n",i,save[i]+1);}}if(flag==0)printf("  No SPF nodes\n");printf("\n");}return 0;
}

?

轉(zhuǎn)載于:https://www.cnblogs.com/chenhuan001/archive/2013/05/13/3075662.html

總結(jié)

以上是生活随笔為你收集整理的poj 1523(无向联通图的割点)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。