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
*/