Submit Info #10056

Problem Lang User Status Time Memory
Dominator Tree cpp yhchang3 AC 63 ms 18.92 MiB

ケース詳細
Name Status Time Memory
example_00 AC 11 ms 14.42 MiB
example_01 AC 10 ms 14.42 MiB
random_00 AC 25 ms 16.30 MiB
random_01 AC 63 ms 18.92 MiB
random_02 AC 19 ms 15.67 MiB
random_03 AC 28 ms 16.92 MiB
random_04 AC 14 ms 14.68 MiB

#include<bits/stdc++.h> using namespace std; const int N = 200010; vector<int> e[N],r[N],g[N]; int inv[N],val[N],sdom[N],idom[N],pre[N],p[N],ans[N],sz,dfn[N]; void init(){for(int i=0;i<=sz;i++) r[i].clear(),g[i]=e[i]=r[i];sz=0;} void dfs(int x){ inv[dfn[x]=val[sz]=sdom[sz]=sz]=x,p[sz]=-1,sz++; for(int u:e[x]){ if(dfn[u]==-1) dfs(u),pre[dfn[u]]=dfn[x]; r[dfn[u]].emplace_back(dfn[x]); } } void comp(int x){ if(p[p[x]]!=-1){ comp(p[x]); if(sdom[val[p[x]]]<sdom[val[x]]) val[x]=val[p[x]]; p[x]=p[p[x]]; } } int find(int x){return p[x]==-1?x:(comp(x),val[x]);} void build(int rt,int n){ for(int i=0;i<=n;i++) dfn[i]=-1,ans[i]=-2;dfs(rt); for(int i=sz-1,q;i>=0;i--){ for(int u:r[i]) sdom[i]=min(sdom[i],sdom[find(u)]); for(int u:g[i]){ q=find(u); if(sdom[q]==i) idom[u]=i; else idom[u]=q; } if(i) g[sdom[i]].emplace_back(i),p[i]=pre[i]; } for(int i=1;i<sz;i++) if(sdom[i]!=idom[i]) idom[i]=idom[idom[i]]; for(int i=1;i<sz;i++) ans[inv[i]]=inv[idom[i]];ans[rt]=-1; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n,m,rt; cin>>n>>m>>rt; for(int i=0,u,v;i<m;i++){ cin>>u>>v; e[u].emplace_back(v); } build(rt,n); for(int i=0;i<n;i++) if(ans[i]==-2) cout<<-1<<' '; else if(ans[i]==-1) cout<<i<<' '; else cout<<ans[i]<<' '; cout<<endl; }