3472537_wa.cpp

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

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

using namespace std;

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

int findSet(int x) {
	if (x != p[x]) {
		return p[x] = findSet(p[x]);
	} else {
		return 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]++;
		}
	}
}

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 < n; i++) {
		if (color[i] == BLACK) {
			lca[u][i] = lca[i][u] = ancestor[findSet(i)];
		}
	}
}

int main() {

	char str[10];
	int i, u, v;

	while (scanf("%d", &n) == 1) {
		for (i = 0; i < n; i++) {
				color[i] = WHITE;
				isRoot[i] = '1';
				cnt[i] = 0;
		}
		for (i = 0; i < n; i++) {
			scanf("%d%s", &u, str);
			u--;
			int cnt = atoi(&str[2]);
			tree[u].clear();
			for (int j = 0; j < cnt; j++) {
				scanf("%d", &v);
				v--;
				tree[u].push_back(v);
				isRoot[v] = '0';
			}
		}
		for (i = 0; i < n; i++) {
			if (isRoot[i] == '1') {
				LCA(i);
				break;
			}
		}
		scanf("%d", &m);
		for (i = 0; i < m; i++) {
			char a[10], b[10];
			scanf("%s%s", a, b);
			u = atoi(&a[1]);
			v = atoi(b);
			cnt[lca[u - 1][v - 1]]++;
		}
		for (i = 0; i < n; i++) {
			if (cnt[i] != 0) {
				printf("%d:%d\n", i + 1, cnt[i]);
			}
		}
	}
	return 0;
}