坑待填。
sun真的wd发现了题解的bug，顺带叉掉了。
等我研究明白了会把这篇题解填好的。
目前先扔代码跑路。
//Love and Freedom. #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define inf 20021225 #define ll long long #define N 200010 #define M 300010 using namespace std; struct edge{int to,lt;}g[M],f[M],t[N],e[N]; int ig[N],it[N],ie[N],in[N],semi[N],idom[N]; int cnt,cng,cne,cnf,sz[N],n,m; // in -> if void add(edge E[],int IN[],int &CNT,int x,int y){E[++CNT].to = y; E[CNT].lt = IN[x]; IN[x] = CNT;} int dfn[N],poi,id[N],fa[N],bel[N],val[N]; void dfs(int x) { dfn[x] = ++poi; id[poi] = x; //printf("MDZZ "); for(int i=ig[x];i;i=g[i].lt) { if(dfn[g[i].to]) continue; dfs(g[i].to); fa[g[i].to] = x; } } int find(int x) { if(bel[x] == x) return x; int rt = find(bel[x]); if(dfn[semi[val[x]]]>dfn[semi[val[bel[x]]]]) val[x] = val[bel[x]]; return bel[x] = rt; } void tarjan() { for(int i=poi;i>=2;i--) { int x = id[i]; for(int j=in[x];j;j=f[j].lt) { int v = f[j].to; if(!dfn[v]) continue; find(v); if(dfn[semi[val[v]]]<dfn[semi[x]]) semi[x] = semi[val[v]]; } add(t,it,cnt,semi[x],x); bel[x] = fa[x]; if(id[i-1] == fa[x]) { x = id[i-1]; for(int j=it[x];j;j=t[j].lt) { int v = t[j].to; find(v);// printf("QAQ"); if(semi[val[v]] == x) idom[v] = x; else idom[v] = val[v]; } } } for(int i=2;i<=poi;i++) { int x = id[i]; if(idom[x] != semi[x]) idom[x] = idom[idom[x]]; } } void getans(int x) { sz[x] = 1; for(int i=ie[x];i;i=e[i].lt) { int y = e[i].to;// if(!sz[y]) getans(y); sz[x] += sz[y]; } } int main() { //freopen("luoguP5180_hackdata.txt","r",stdin); //freopen("test.txt","w",stdout); scanf("%d%d",&n,&m); int x,y; for(int i=1;i<=n;i++) semi[i] = bel[i] = val[i] = i; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); add(g,ig,cng,x,y); add(f,in,cnf,y,x); } dfs(1); tarjan(); for(int i=2;i<=n;i++) if(idom[i]) add(e,ie,cne,idom[i],i); getans(1); for(int i=1;i<=n;i++) printf("%d ",sz[i]); return 0; }