tarjan縮点-人気の牛-ノート
1646 ワード
tarjanテンプレート?Emmmm,洛谷P 2341.いくつかのテンプレートに対する解釈はコード注釈にあります.
#include/// hzwer ,%%%hzwer
#include
#include
#include
#include
#define MAXN 10005
#define MAXM 50005
using namespace std;
struct data{
int to,next;
}e[MAXM],d[MAXM];
int head[MAXN];
int n,m,cnt,top;
int dfn[MAXN],low[MAXN],q[MAXN];
int scc,h[MAXN],belong[MAXN],hav[MAXN];
bool vis[MAXN],inq[MAXN];
int ans;
void dfs(int a){
int now;
vis[a]=inq[a]=1;
low[a]=dfn[a]=++cnt;
q[++top]=a;
int c=head[a];
while(c){///
if(!vis[e[c].to ]){
dfs(e[c].to );
low[a]=min(low[a],low[e[c].to ]);
}
else if(inq[e[c].to ]) low[a]=min(low[a],dfn[e[c].to ]);
c=e[c].next ;
}
if(low[a]==dfn[a]){//// a SCC
scc++;
while(now!=a){//// SCC
now=q[top--];
inq[now]=0;
belong[now]=scc;
++hav[scc];
}
}
}
void rebuild(){///SCC ,
cnt=0;
for(int i=1;i<=n;i++){
int c=head[i];
while(c){//// i
if(belong[i]!=belong[e[c].to]){
d[++cnt].to =belong[e[c].to ];
d[cnt].next =h[belong[i]];
h[belong[i]]=cnt;
}
c=e[c].next ;
}
}
}
void tarjan(){
for(int i=1;i<=n;i++) if(!vis[i]) dfs(i);
rebuild();
}
void work(){
for(int i=1;i<=scc;i++)
if(!h[i]){/////
if(ans){
ans=0;return;
}
else ans=hav[i];
}
}
int main(){
scanf("%d%d",&n,&m);
int a,b;
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
e[++cnt].to =b;
e[cnt].next =head[a];
head[a]=cnt;
}
tarjan();
work();
printf("%d",ans);
return 0;
}