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
| #include <iostream> #include <cstdio> #include <vector> #include <queue> using namespace std; int n, uu, fa[65545][17], sta[65545], din, dep[65545], siz[65545]; int ru[65545]; queue<int> d; struct Graph{ vector<int> v[65545]; void add_edge(int fro, int too){ v[fro].push_back(too); } }ga, gb; int lca(int x, int y){ if(dep[x]<dep[y]) swap(x, y); for(int i=15; i>=0; i--) if(dep[fa[x][i]]>=dep[y]) x = fa[x][i]; if(x==y) return x; for(int i=15; i>=0; i--) if(fa[x][i]!=fa[y][i]){ x = fa[x][i]; y = fa[y][i]; } return fa[x][0]; } int main(){ cin>>n; for(int i=1; i<=n; i++){ while(scanf("%d", &uu)!=EOF){ if(!uu) break; ga.add_edge(i, uu); gb.add_edge(uu, i); ru[i]++; } if(!ru[i]) d.push(i); } while(!d.empty()){ int x=d.front(); d.pop(); sta[++din] = x; for(int i=0; i<gb.v[x].size(); i++){ int t=gb.v[x][i]; ru[t]--; if(!ru[t]) d.push(t); } } for(int i=1; i<=n; i++){ int x=sta[i], l; if(ga.v[x].size()) l = ga.v[x][0]; else l = 0; for(int j=1; j<ga.v[x].size(); j++) l = lca(l, ga.v[x][j]); fa[x][0] = l; dep[x] = dep[l] + 1; for(int j=1; j<=15; j++) fa[x][j] = fa[fa[x][j-1]][j-1]; } for(int i=n; i; i--){ int x=sta[i]; siz[x]++; siz[fa[x][0]] += siz[x]; } for(int i=1; i<=n; i++) printf("%d\n", siz[i]-1); return 0; }
|