195
poj 1144 Network 关节点
Tarjan练手题，WA了两次，处理回边误把low[u]=min(low[u],dph[v]); 写成low[u]=min(low[u],low[v]);了，还要注意节点数小于2时输出0
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
int n,ans;
vector<int> node[101];
int dph[101],low[101],vis[101];
void dfs(int v,int d)
{
dph[v]=low[v]=d;
vis[v]=1;
int u,ok=0;
for(int i=0;i<node[v].size();i++)
{
u=node[v][i];
if(vis[u])
{
low[v]=min(low[v],dph[u]);
}
else
{
dfs(u,d+1);
if(low[u]>=dph[v])ok++;
low[v]=min(low[v],low[u]);
}
}
if(v!=1)ok++;
if(ok>1)ans++;
}
int main()
{
while(~scanf("%d",&n)&&n)
{
int v,u,i;
for(i=1;i<=n;i++)node[i].clear();
while(scanf("%d",&v)&&v)
{
while(getchar()!='\n')
{
scanf("%d",&u);
node[v].push_back(u);
node[u].push_back(v);
}
}
ans=0;
memset(vis,0,sizeof(vis));
dfs(1,0);
printf("%d\n",ans);
}
}
最后更新：2017-04-03 16:48:59