1144.c

来自「北大ACM网站 1144题 http://acm.pku.edu.cn/Jud」· C语言 代码 · 共 65 行

#include <stdio.h>
#include <string.h>

char net[101][101];
char visit[101];
int n;

void dfs(int x)
{
	int i;
	for (i = 1; i <= n; i++)
		if (net[x][i] == 1 && !visit[i])
		{
			visit[i] = 1;
			dfs(i);
		}
}

int count(int x)
{
	int i, res = 0;
	memset(visit, 0, sizeof(visit));
	visit[x] = 1;
	for (i = 1; i <= n; i++)
		if (!visit[i])
		{
			visit[i] = 1;
			res++;
			dfs(i);
		}
	return res;
}

int main(void)
{
	int i, j, size, res;
	char c;

	while (scanf("%d", &n), n)
	{
		memset(net, 0, sizeof(net));
		while (scanf("%d%c", &i, &c), i)
			do {
				scanf("%d%c", &j, &c);
				net[i][j] = net[j][i] = 1;
			} while (c != '\n');
		size = count(0);
		res = 0;
		for (i = 1; i <= n; i++)
		{		
			for (j = 1; j <= n; j++)
				if (net[i][j] == 1)
					net[i][j] = net[j][i] = 2;
			if (count(i) > size)
				res++;
			for (j = 1; j <= n; j++)
				if (net[i][j] == 2)
					net[i][j] = net[j][i] = 1;
		}
		printf("%d\n", res);
	}

	return 0;
}