3799887_wa.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 114 行

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

using namespace std;

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

vector < vector <node> > map;

int p, c;
int dfn[10000];
int fat[10000];
int low[10000];
int num;

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

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

	dfn[u] = low[u] = num++;
	fat[u] = fa;
	for (i = 0; i < map[u].size(); i++)
	{
		if (dfn[map[u][i].tar] == -1)
		{
			map[u][i].visited = 1;
			dfs(map[u][i].tar, u);
			low[u] = min(low[u], low[map[u][i].tar]);
		}
		else
		{
			if (map[u][i].tar != fa)
			{
				low[u] = min(low[u], dfn[map[u][i].tar]);
			}
		}
	}
}

int main()
{
	int i, j;
	int u, v;

	while (true)
	{
		scanf("%d%d", &p, &c);
		if (p == 0 && c == 0)
		{
			break;
		}
		map.resize(p);
		for (i = 0; i < p; i++)
		{
			map[i].clear();
		}
		for (i = 0; i < c; i++)
		{
			scanf("%d%d", &u, &v);
			map[u].push_back(node(v, 0));
			map[v].push_back(node(u, 0));
		}
		num = 0;
		int tot = 0;
		int ans = 0;
		memset(dfn, -1, sizeof(dfn));
		for (i = 0; i < p; i++)
		{
			if (dfn[i] == -1)
			{
				dfs(i, -1);
				tot++;
			}
		}
		for (i = 0; i < p; i++)
		{
			int mark = 0;
			for (j = 0; j < map[i].size(); j++)
			{
				if (map[i][j].tar == fat[i])
					continue;
				if (low[map[i][j].tar] < dfn[i])
				{
					mark = 1;
					break;
				}
			}
			if (mark == 1)
				continue;
			int tmp = tot - 1 + (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 > ans)
				ans = tmp;
		}
		printf("%d\n", ans);
	}
	return 0;
}