4191134_ac_16ms_252k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <map>
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

map <int, int> h;
int cnt;

struct node
{
	int tar;
	int visited;
	node (int t, int v)	:tar(t), visited(v) {}
};

vector <node> MAP[1001];

int dfn[1001];
int fat[1001];
int low[1001];
int id[1001];

void insert(int u, int v)
{
	if (h[u] == 0)
	{
		h[u] = cnt++;
	}
	if (h[v] == 0)
	{
		h[v] = cnt++;
	}
	id[h[u]] = u;
	id[h[v]] = v;
	MAP[h[u]].push_back(node(h[v], 0));
	MAP[h[v]].push_back(node(h[u], 0));
}

int min(int a, int b)
{
	return a < b ? a : b;
}

int num;

int dfs(int u, int fa)
{
	int i, tmp;

	if (dfn[u] != -1)
		return dfn[u];

	dfn[u] = low[u] = num++;
	fat[u] = fa;
	for (i = 0; i < MAP[u].size(); i++)
	{
		if (MAP[u][i].tar == fa)
			continue;
		tmp = num;
		int reach = dfs(MAP[u][i].tar, u);
		if (reach < low[u])
			low[u] = reach;
		else
		{
			if (reach == dfn[u] || reach == tmp)
			{
				MAP[u][i].visited = 1;
			}
		}
	}
	return low[u];
}

int main()
{
	int u, v, i, j;
	int now = 1;

	while (true)
	{
		h.clear();
		cnt = num = 1;
		for (i = 0; i < 1001; i++)
			MAP[i].clear();
		scanf("%d", &u);
		if (u == 0)
		{
			break;
		}
		printf("Network #%d\n", now++);
		scanf("%d", &v);
		insert(u, v);
		while (true)
		{
			scanf("%d", &u);
			if (u == 0)
			{
				break;
			}
			scanf("%d", &v);
			insert(u, v);
		}
		int tot = 0;
		memset(dfn, -1, sizeof dfn);
		for (i = 1; i < cnt; i++)
		{
			if (dfn[i] == -1)
			{
				dfs(i, -1);
				tot++;
			}
		}
		vector <pair <int, int> > ans;
		for (i = 1; i < cnt; i++)
		{
			int tmp = tot - (fat[i] == -1);
			for (j = 0; j < MAP[i].size(); j++)
			{
				if (MAP[i][j].tar == fat[i])
					continue;
				tmp += MAP[i][j].visited;
			}
			if (tmp != 1)
			{
				ans.push_back(make_pair(id[i], tmp));
			}
		}
		if (ans.size() == 0)
			puts("  No SPF nodes");
		else
		{
			for (i = 0; i < ans.size(); i++)
			{
				printf("  SPF node %d leaves %d subnets\n", ans[i].first, ans[i].second);
			}
		}
		puts("");
	}
	return 0;
}