3453441_ac_454ms_304k.cpp

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

#include <stdio.h>
#include <ctype.h>
#include <queue>
#include <string.h>
#include <vector>
#include <algorithm>
#define maxn 1601

using namespace std;

int n;
vector <int> tree[maxn];
int d[maxn];
queue <int> que;
int ans;

void solve()
{
	int i, u, v, no;

	for (i = 0; i < n; i++)
	{
		if (d[i] == 1)
		{
			d[i] = 0;
			que.push(i);
		}
	}
	while (!que.empty())
	{
		u = que.front();
		que.pop();
		no = 1;
		for (i = 0; i < tree[u].size(); i++)
		{
			v = tree[u][i];
			if (d[v] != 0)
			{
				no = -1;
				break;
			}
		}
		if (no == 1)
		{
			continue;
		}
		ans++;
		d[v] = 0;
		for (i = 0; i < tree[v].size(); i++)
		{
			if (d[tree[v][i]] != 0)
			{
				d[tree[v][i]]--;
				if (d[tree[v][i]] == 1)
				{
					que.push(tree[v][i]);
				}
			}
		}
	}
}

int main()
{
	int i, j, u, v, num;
	char str[10];

	while (scanf("%d", &n) == 1)
	{
		ans = 0;
		for (i = 0; i < n; i++)
		{
			d[i] = 0;
			tree[i].clear();
		}
		for (i = 0; i < n; i++)
		{
			scanf("%d", &u);
			scanf("%s", str);
			for (j = 0; str[j]; j++)
			{
				if (isdigit(str[j]))
				{
					break;
				}
			}
			num = atoi(&str[j]);
			d[u] += num;
			for (j = 0; j < num; j++)
			{
				scanf("%d", &v);
				d[v]++;
				tree[u].push_back(v);
				tree[v].push_back(u);
			}
		}
		solve();
		printf("%d\n", ans);
	}
	return 0;
}