一直都在复习联赛，都没有时间学习LCA了，今天我好不容易抽了一点时间，学习了LCA。这道题目十分的水，随随便摆就过掉了，没有什么难点，只要你会Tarjan你就可以轻易的过掉。好了，闲话不多说，直接上代码
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<map> #include<set> #include<vector> #include<algorithm> using namespace std; #define REP(i, a, b) for(int i = (a), _end_ = (b);i <= _end_; ++ i) #define str(a) strlen(a) #define mem(a) memset((a), 0, sizeof(a)) const int maxn = 1010; int n, m; vector<int> Edge[maxn]; int sum[maxn], ans[maxn], fa[maxn], Map[maxn][maxn]; bool vis[maxn]; int cha(int x) { return x == fa[x] ? x : fa[x] = cha(fa[x]); } void Tarjan(int x) { REP(i, 1, n) if(vis[i] && Map[x][i]) ans[cha(i)] += Map[x][i]; vis[x] = true; fa[x] = x; REP(i, 0, Edge[x].size() - 1) { Tarjan(Edge[x][i]); fa[Edge[x][i]] = x; } } int main() { while(~scanf("%d", &n)) { REP(i, 1, n) Edge[i].clear(); mem(sum);mem(ans);mem(Map);mem(vis); int x, y; REP(i, 1, n) { scanf("%d:(%d)", &x, &m); REP(i, 1, m) { scanf("%d", &y); ++sum[y]; Edge[x].push_back(y); } } scanf("%d", &m); REP(i, 1, m) { scanf(" (%d %d)", &x, &y); ++Map[x][y];++Map[y][x]; } REP(i, 1, n) if(!sum[i]) { Tarjan(i); break; } REP(i, 1, n) if(ans[i]) printf("%d:%d\n", i, ans[i]); } return 0; }