http://poj.org/problem?id=1144
題意很簡單,已知圖中各邊的連接配接情況,求割點的個數。
注意輸入格式。。
#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
vector<int> edge[110];
int dfn[110];//記錄節點被通路的深度
int vis[110];//記錄該節點目前的狀态,0表示未通路,1表示在棧中,2表示已經通路過
int low[110];//該節點可以到達的通路時間最早的祖先
int n;
int root;//根節點編号
int sum;//割點個數
int ok[110];
//在深度周遊過程中,記錄每個節點的深度,對目前節點s以及和它相連的節點t,有以下兩種情況:
//t沒被通路過,這時遞歸節點t,并用t通過非樹枝邊可以到達的最早的祖先來更新s的low值;
//t目前在棧中,這時說明圖中有一個環,用t的深度來更新s的low值,
//s是割點的條件:s是根且有大于一個的兒子(用son來計數),或s不是根,且s有一個兒子i滿足low[i] >= dfn[s];
void dfs(int s, int father, int dep)
{
int son = 0;
vis[s] = 1;
dfn[s] = low[s] = dep;
for(int i = 0; i < (int)edge[s].size(); i++)
{
int t = edge[s][i];
if(vis[t] == 1 && t != father)
low[s] = min(low[s],dfn[t]);
if(vis[t] == 0)
{
dfs(t,s,dep+1);
son++;
low[s] = min(low[s],low[t]);
if((s == root && son > 1) ||(s != root && dfn[s] <= low[t]))
ok[s] = 1;
}
}
vis[s] = 2;
}
int main()
{
int u,v;
while(~scanf("%d",&n) && n)
{
for(int i = 1; i <= n; i++)
edge[i].clear();
memset(dfn,0,sizeof(dfn));
memset(vis,0,sizeof(vis));
memset(low,0,sizeof(low));
memset(ok,0,sizeof(low));
sum = 0;
while(~scanf("%d",&u) && u)
{
while(getchar() != '\n')
{
scanf("%d",&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
}
root = 1;
dfs(1,-1,1);
for(int i = 1; i <= n; i++)
if(ok[i])
sum++;
printf("%d\n",sum);
}
return 0;
}