UVA - 315 Network （割点模板+stringstream）

链接：https://cn.vjudge.net/problem/UVA-315

题意：求无向图割点的个数。

思路：tarjan算法。搜索的时候，假设当前搜索到的节点为u，检验一下其孩子节点v的lowv，如果lowv>=dfnu,那么u有可能是一个点。如果u是根节点，那么其孩子数目大于等于2，他才是一个割点。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 110;
const int M = 1e4+10;
int n,x,head[N],cnt,dfn[N],id,num;
bool cut[N];
struct Edge
{
	int to,nxt;
}g[M];
void Init()
{
	id=num=cnt=0;
	for(int i=1;i<=n;i++)
		cut[i]=dfn[i]=0,head[i]=-1;	
	return ;
}
void add(int u,int v)
{
	g[cnt].to=v; g[cnt].nxt=head[u]; head[u]=cnt++;
	return ;	
} 
int tarjan(int u,int fa)
{
	int v,child=0,lowu,lowv;
	dfn[u]=++id;  
	lowu=dfn[u];
	for(int i=head[u];i!=-1;i=g[i].nxt)
	{
		v=g[i].to;
		if(!dfn[v])
		{
			child++;
			lowv=tarjan(v,u);
			lowu=min(lowu,lowv);
			if(lowv>=dfn[u])//等于时也是割点！！！！！！！ 
				cut[u]=1;	
		}
		else if(v!=fa)
			lowu=min(lowu,dfn[v]);
	}
	if(fa==0&&child<2)
		cut[u]=0;
	return lowu;
}
int main(void)
{
	int u,v;
	string s;
	stringstream ss;
	while(~scanf("%d",&n)&&n)
	{
		getchar();
		Init();
		while(getline(cin,s))
		{
			ss.clear();
			ss.str(s);
			ss>>u;
			if(u==0) break;
			while(1)
			{
				
				ss>>v;
				if(ss.fail()) break;
				add(u,v);
				add(v,u);
			}	
		}
		for(int i=1;i<=n;i++)
			if(!dfn[i]) tarjan(i,0);

		for(int i=1;i<=n;i++)
			if(cut[i]) num++;
		printf("%d\n",num);	
	}
	return 0;	
} 
/*
5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
*/