1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
| #include<cstdio> #include<vector> #include<iostream> #include<cstring> using namespace std; #define rep(i,a,n) for(int i=(a);i<(n);i++) #define per(i,a,n) for(int i=(n-1);i>=(a);i--) #define fi first #define se second typedef pair <int,int> pII; typedef long long ll; const int INF = 0x3f3f3f3f;
int T,n,cnt; const int maxn = 1e4+10; struct node{ int next,to; }G[maxn<<1]; int head[maxn],fa[maxn],vis[maxn],ans[maxn]; void init(){ cnt = 0; memset(head,-1,sizeof(head)); memset(fa,0,sizeof(fa)); memset(vis,0,sizeof(vis)); rep(i,1,n+1) fa[i] = i; } void add(int u,int v){ G[cnt].to = v; G[cnt].next = head[u]; head[u] = cnt++; } int find(int x){ if(fa[x]!=x) fa[x] = find(fa[x]); return fa[x]; } struct Query{ int to,id; Query(){} Query(int _to,int _id){ to = _to; id = _id; } }; vector<Query> query[maxn]; void dfs(int now){ int u,v; vis[now] = 1; for(int i=head[now];~i;i=G[i].next){ v = G[i].to; if(vis[v]) continue; dfs(v); fa[v] = now; } for(int i = 0;i<query[now].size();i++){ Query node = query[now][i]; u = node.to; int id = node.id; if(vis[u] == 2){ ans[find(u)] ++; } } vis[now] = 2; } int vvis[maxn]; int main(){ #ifdef LOCAL freopen("1.in","r",stdin); #endif while(~scanf("%d",&n)){ memset(head,-1,sizeof(head)); cnt = 0; memset(vis,0,sizeof(vis)); memset(vvis,0,sizeof(vvis)); memset(ans,0,sizeof(ans)); rep(i,1,n+1) query[i].clear(); rep(i,1,n+1) fa[i] = i; int root = 0; rep(i,0,n){ int u,x,v;scanf("%d",&u); scanf("%*c%*c%d%*c",&x); rep(i,0,x){ scanf("%d",&v); add(u,v); vvis[v] = 1; } } rep(i,1,n+1){ if(vvis[i]==0){ root = i; break; } } int m;scanf("%d",&m); char ch; rep(i,0,m){ ch = getchar(); while(ch!='(') ch = getchar(); int u,v;scanf("%d%d",&u,&v); query[u].push_back(Query(v,i)); query[v].push_back(Query(u,i)); while(ch!=')') ch = getchar(); } dfs(root); rep(i,1,n+1){ if(ans[i]){ printf("%d:%d\n",i,ans[i]); } } } return 0; }
|