POJ1144(割点入门题)

Description

Input

Output

Sample Input

5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
0

Sample Output

1
2

Hint

Source

Central Europe 1996

你只要记住：：（剩下的代码中解释）

1.如果点v是DFS序列的根节点，则如果v有一个以上的孩子，则v是一个割点。

2.如果v不是DFS序列根节点，并且点v的任意后继u能追溯到最早的祖先节点low[u]>=dfn[v]，则v是一个割点。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct ***
{
	int to, ne;
}es[10005];
int head[100];
int e;
void add(int u, int v)
{
	es[e].to = v;
	es[e].ne = head[u];
	head[u] = e++;
}
int root;
int ans;
int dfn[105];
int low[105];//最早返祖节点；
int vis[105];
int ar[105];
int time;
void tarjan(int u, int fa)
{
	int son = 0; //子孙数量
	vis[u] = 1;//标记已经被访问过
	dfn[u] = low[u] = ++time;
	for (int s = head[u]; ~s; s = es[s].ne)
	{
		int v = es[s].to;//找到子孙节点；
		if (!vis[v])//如果这个不是曾经的祖宗
		{
			tarjan(v, u);//遍历
			son++;//子孙++
			low[u] = min(low[u], low[v]);//如果子孙能够回溯到更早的~~那么父亲辈的他也行~~
			if (u == root&&son > 1 || u != root&&dfn[u] <= low[v])//如之前所言~
			{
				ar[u] = 1;
			}
		}
		if (vis[v] && v != fa)
		{
			low[u] = min(low[u], dfn[v]);
		}
	}
}
int main()
{
	int n;
	while (~scanf("%d", &n) && n)
	{
		memset(vis, 0, sizeof(vis));
		memset(head, -1, sizeof(head));
		memset(dfn, 0, sizeof(dfn));
		memset(low, 0, sizeof(low));
		memset(ar, 0, sizeof(ar));
		e = 0;
		time = 0;
		ans = 0;
		int u, v;
		while (scanf("%d", &u) && u)
		{
			while (getchar() != '\n')
			{
				scanf("%d", &v);
				add(u, v);
				add(v, u);
			}
		}
		root = 1;
		tarjan(root, -1);
		int ans=0;
		for (int s = 1; s <= n; s++)
		{
			if (ar[s])
			{
				ans++;
			}
		}
		cout << ans << endl;
	}
	return 0;
}