学步园

题目大意：求一个无向图的割点，并把割点连接的连通个数求出来

解题思路：tarjan算法求割点

这里定义：

Low(u)为u或u的子树中能通过非父子边追溯到的最早的节点，即DFS序号最小的节点。根据定义，则有：

Low(u)=Min
{
DFS(u)
DFS(v) (u,v)为后向边(返祖边) 等价于 DFS(v)<DFS(u)且v不为u的父亲节点
Low(v) (u,v)为树枝边(父子边)
}

满足割点的条件有：

一个顶点u是割点，当且仅当满足(1)或(2)
(1) u为树根，且u有多于一个子树。
(2) u不为树根，且满足存在(u,v)为树枝边(或称父子边，即u为v在搜索树中的父亲)，使得DFS(u)<=Low(v)。

所以用一个cnt[i]保存i点连接的连通分量个数

由于0作为根节点，所以cnt[0] = 0;

其他节点初始化为1

当dfs[u] <= low[v]时，(u,v)为树枝边，cnt[u]++

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

struct node
{
	int v, next;
};

const int maxn = 1010;

int head[maxn], e, index, num, cnt[maxn], dfn[maxn], low[maxn];
node edge[maxn * maxn];

void addEdge(int u, int v);
void init();
void tarjan(int u);

int main()
{
	int u, v, t = 0;
	init();
	while(scanf("%d", &u) != EOF && u != 0)
	{
		t++;
		scanf("%d", &v);
		u--; v--;
		addEdge(u, v);
		num = max(num, max(u, v));
		while(scanf("%d", &u) != EOF && u != 0)
        {
            scanf("%d", &v);
            num = max(num, max(u, v));
            u--; v--;
            addEdge(u, v);
        }
        cnt[0] = 0;
        for(int i = 1; i < num; i++)
        	cnt[i] = 1;
        tarjan(0);
        printf("Network #%d\n", t);
        bool flag = false;
        for(int i = 0; i < num; i++)
        {
			if(cnt[i] > 1)
			{
				flag = true;
				printf("  SPF node %d leaves %d subnets\n", i + 1, cnt[i]);
			}
		}
		if(!flag)
			printf("  No SPF nodes\n");
		printf("\n");
		init();
	}
		return 0;
}

void addEdge(int u, int v)
{
    edge[e].v = v;
    edge[e].next = head[u];
    head[u] = e++;
    edge[e].v = u;
    edge[e].next = head[v];
    head[v] = e++;
}

void init()
{
	memset(head, -1, sizeof(head));
	memset(dfn, -1, sizeof(dfn));
	e = 0;
	index = 0;
	num = 0;
}

void tarjan(int u)
{
	dfn[u] = low[u] = index++;
	for(int i = head[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].v;
		if(dfn[v] == -1)
		{
			tarjan(v);
			if(dfn[u] <= low[v])
				cnt[u]++;
			else
				low[u] = min(low[u], low[v]);
		}
		else
			low[u] = min(low[u], dfn[v]);
	}
}