3473242_ac_610ms_5556k.cc

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

#include <stdio.h>
#include <vector>
#include <ctype.h>
#include <algorithm>
#define WHITE 0
#define BLACK 1

using namespace std;

int n, m;
vector <int> tree[901], s[901];
int color[901], isRoot[901];
int ancestor[901], p [901], rank[901];
int cnt[901];

int findSet(int x) {
	if (x != p[x]) {
		p[x] = findSet(p[x]);
	} 
	return p[x];
}

void link(int x, int y) {
	if (rank[x] > rank[y]) {
		p[y] = x;
	} else {
		p[x] = y;
		if (rank[x] == rank[y]) {
			rank[y]++;
		}
	}
}
int yes[901][901];

void LCA(int u) {
	int i;

	p[u] = u;
	rank[u] = 0;
	ancestor[findSet(u)] = u;
	for (i = 0; i < tree[u].size(); i++) {
		int v = tree[u][i];
		LCA(v);
		link(findSet(u), findSet(v));
		ancestor[findSet(u)] = u;
	}
	color[u] = BLACK;
	for (i = 0; i < s[u].size(); i++) {
		int v = s[u][i];
		if (color[v] == BLACK) {
			cnt[ancestor[findSet(v)]] += yes[u][v];
		}
	}
}


int check(int u, int v)
{
	int ret = yes[u][v];
	yes[u][v]++;
	yes[v][u]++;
	return !ret;
}

int main() {

	char ch;
	int i, j, u, v;
	char tmp[1000];

	while (scanf("%d", &n) == 1) {
		for (i = 0; i < n; i++) {
				color[i] = WHITE;
				isRoot[i] = 1;
				cnt[i] = 0;
				tree[i].clear();
				s[i].clear();
		}
		memset(yes, 0, sizeof(yes));
		for (i = 0; i < n; i++) {
			scanf("%d", &u);
			u--;
			while (1)
			{
				ch = getchar();
				if (ch == '(')
					break;
			}
			int cnt;
			scanf("%d", &cnt);
			while (1)
			{
				ch = getchar();
				if (ch == ')')
					break;
			}
			for (int j = 0; j < cnt; j++) {
				scanf("%d", &v);
				v--;
				tree[u].push_back(v);
				isRoot[v] = 0;
			}
		}
		scanf("%d", &m);
		u = v = -1;
		while (m)
		{
			gets(tmp);
			for (i = 0; tmp[i]; i++)
			{
				if (isdigit(tmp[i]))
				{
					j = i;
					int t = 0;
					while (tmp[j] && isdigit(tmp[j]))
					{
						t *= 10;
						t += (tmp[j] - '0');
						j++;
					}
					i = j - 1;
					if (u == -1)
						u = t;
					else
					{
						v = t;
						u--;v--;
						if (u == v)
						{
							cnt[u]++;
							m--;
							u = v = -1;
							continue;
						}
						if(check(u, v))
						{
							s[u].push_back(v);
							s[v].push_back(u);
						}
						u = v = -1;
						m--;
					}
				}
			}
		}
		for (i = 0; i < n; i++) {
			if (isRoot[i]) {
				LCA(i);
				break;
			}
		}
		for (i = 0; i < n; i++) {
			if (cnt[i] != 0) {
				printf("%d:%d\n", i + 1, cnt[i]);
			}
		}
	}
	return 0;
}