ジョイントポイント

深さ探索遡及時処理low&&dfn
zoj 1119を例に

/*
* this code is made by LinMeiChen
* Problem:
* Type of Problem:
* Thinking:
* Feeling:
*/
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
#include<list>
using namespace std;
typedef long long lld;
typedef unsigned int ud;
#define oo 0x3f3f3f3f
#define maxn 1010
int map[maxn][maxn];
int dfn[maxn], mark[maxn];
int low[maxn], subnets[maxn];
int nodes, g_dfn, s, son;

void DFS(int u)
{
	mark[u] = 1;
	for (int v = 1; v <= nodes; v++)
	{
		if (map[u][v])
		{
			if (!mark[v])
			{
				low[v] = dfn[v] = ++g_dfn;
				DFS(v);
				low[u] = min(low[v], low[u]);
				if (low[v] >= dfn[u])
				{
					if (u == s)
						son++;
					else
						subnets[u]++;
				}
			}
			else
				low[u] = min(low[u], dfn[v]);
		}
	}
}

int main()
{
	int u, v;
	s = 1;
	for (int cas = 1;true;cas++)
	{
		memset(map, 0, sizeof map);
		memset(subnets, 0, sizeof subnets);
		memset(mark, 0, sizeof mark);
		memset(low, 0, sizeof low);
		memset(dfn, 0, sizeof dfn);		
		low[s] = dfn[s] = 1;
		g_dfn = 1;
		nodes = 0;
		son = 0;

		scanf("%d", &u);
		if (u == 0)
			break;
		scanf("%d", &v);
		map[u][v] = map[v][u] = 1;
		nodes = max(max(nodes, u), v);
		while (true)
		{
			scanf("%d", &u);
			if (u == 0)
				break;
			scanf("%d", &v);
			map[u][v] = map[v][u] = 1;
			nodes = max(max(nodes, u), v);
		}

		DFS(s);

		if (cas > 1)
			puts("");
		printf("Network #%d
", cas);
		if (son > 1)
			subnets[s] = son - 1;
		bool find = false;
		for (int i = 1; i <= nodes; i++)
		{
			if (subnets[i])
			{
				printf("  SPF node %d leaves %d subnets
", i, subnets[i] + 1);
				find = true;
			}
		}
		if (!find)
			printf("  No SPF nodes
");
	}
	return 0;
}