3723052_wa.cpp

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

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

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, u, v;

	scanf("%d", &n);
	ans = 0;
	for (i = 0; i < n; i++)
	{
		d[i] = 0;
		tree[i].clear();
	}
	for (i = 0; i < n - 1; i++)
	{
		scanf("%d%d", &v, &u);
		u--;v--;
		d[u]++;
		d[v]++;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}
	solve();
	printf("%d\n", ans);
	return 0;
}