3472974_wa.cc

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

#include <stdio.h>
#include <vector>
#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]) {
		return p[x] = findSet(p[x]);
	} else {
		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]++;
		}
	}
}

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)]]++;
		}
	}
}

void Readin(int& i,int& j) {
    char str[10];
    scanf("%s",str);
    memcpy(str,str+1,strlen(str));
    sscanf(str,"%d",&i);
    scanf("%s",str);
    sscanf(str,"%d",&j);
}

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;
				tree[i].clear();
				s[i].clear();
		}
		for (i = 0; i < n; i++) {
			scanf("%d%s", &u, str);
			u--;
			int cnt = atoi(&str[2]);
			for (int j = 0; j < cnt; j++) {
				scanf("%d", &v);
				v--;
				tree[u].push_back(v);
				isRoot[v] = 0;
			}
		}
		scanf("%d", &m);
		for (i = 0; i < m; i++) {
			Readin(u, v);
			u--;v--;
			s[u].push_back(v);
			s[v].push_back(u);
		}
		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;
}