zju1119 SPF

终于写好无向图找割点了，笔记一下

割点的充分必要条件是
1. 对于dfs搜索树的根，有至少两个子树
2. 对于非dfs树的根，有至少一个子树

p.s.其实这两个条件是一样的，因为对于非根节点，有一条边连到父节点，所以把它看成是树根的时候，就有至少两个子树了

#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <stack>
using namespace std;

vector<vector<int> > g;
set<int> node;

vector<int> dfn, low, sub;
int cnt;
void dfs(int u)
{
	dfn[u] = low[u] = cnt++;
	for (int i = 0; i < g[u].size(); ++i)
	{
		int v = g[u][i];
		if (dfn[v] == -1) {
			dfs(v);
			low[u] = min(low[u], low[v]);
			if (dfn[u] <= low[v])
				++sub[u];
		} else {
			low[u] = min(low[u], dfn[v]);
		}
	}
}

int main()
{
	int tcs = 1, u, v;
	while (true)
	{
		g.clear();
		node.clear();
		bool read = false;
		while (scanf("%d", &u), u != 0)
		{
			read = true;
			scanf("%d", &v);
			int t = max(u, v) + 1;
			t = max((int)g.size(), t);
			g.resize(t);
			g[u].push_back(v);
			g[v].push_back(u);
			node.insert(u);
			node.insert(v);
		}
		if (!read)
			break;
			
		dfn.assign(g.size(), -1);
		low.assign(g.size(), 0);
		sub.assign(g.size(), 0);
		cnt = 0;
		int root = *node.begin();
		dfs(root);
		--sub[root];
		if (tcs > 1)
			printf("\n");
		printf("Network #%d\n", tcs++);
		bool has = false;
		for (int i = 0; i < g.size(); ++i)
			if (sub[i] >= 1)
			{
				has = true;
				printf("  SPF node %d leaves %d subnets\n", i, sub[i] + 1);
			}
		if (!has)
			printf("  No SPF nodes\n");
	}
	
	return 0;
}