application of Kosaraju algorithm
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
const int M = 5e4 + 10, N = 1e4 + 10;
int e[M], ne[M], h[N], idx, sccNo[N], outdeg[N], color[N], re[M], rne[M], rh[N], curScc, ans[N];
stack<int> order;
enum COLOR {
WHITE, GRAY, BLACK
};
void addArc(int x, int y){
e[idx] = y;
re[idx] = x;
ne[idx] = h[x];
rne[idx] = rh[y];
h[x] = idx;
rh[y] = idx;
idx ++;
}
void dfs1(int u){
color[u] = GRAY;
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(color[j] == WHITE){
dfs1(j);
}
}
color[u] = BLACK;
order.push(u);
}
void dfs2(int u){
color[u] = GRAY;
sccNo[u] = curScc;
ans[curScc] ++;
for(int i = rh[u]; i != -1; i = rne[i]){
int j = re[i];
if(color[j] == WHITE){
dfs2(j);
}
}
color[u] = BLACK;
}
void mark_scc(int n){
//perform dfs on G
for(int i = 1; i <= n; i ++){
if(color[i] == WHITE)dfs1(i);
}
memset(color, 0, sizeof color);
//perform dfs on G transpose
while(order.size()){
int t = order.top();
order.pop();
if(color[t] == WHITE){
dfs2(t);
curScc ++;
}
}
}
void construct_dag(int n){
for(int i = 1; i <= n; i ++){
for(int j = h[i]; j != -1; j = ne[j]){
int k = e[j];
if(sccNo[k] == sccNo[i])continue;
outdeg[sccNo[i]] ++;
}
}
}
void solve(int n){
mark_scc(n);
construct_dag(n);
int cnt = 0, res = 0;
for(int i = 0; i < curScc; i ++){
if(outdeg[i] == 0){
cnt ++;
res = ans[i];
}
if(cnt == 2){
res = 0;
break;
}
}
cout << res << endl;
}
int main(){
int n, m;
cin >> n >> m;
memset(h, -1, sizeof h);
memset(rh, -1, sizeof rh);
while(m--){
int x, y;
cin >> x >> y;
addArc(x, y);
}
solve(n);
return 0;
}