不知道那里假了,求hack。
大样例过不了,能不能给个小一点的hack
#include<bits/stdc++.h>
using namespace std;
const long long MX=10000100,INF=0x3f3f3f3f;
vector<long long>vec[MX];
long long low[MX]={0},dfn[MX]={0},siz[MX]={0},tim=0;
long long belong[MX]={0},cnt=0;
long long flag[MX]={0};stack<long long>st;
void tarjan(int now){
dfn[now]=++tim,low[now]=tim;st.push(now);flag[now]=1;
for(auto to:vec[now]){
if(!dfn[to]){
tarjan(to);
low[now]=min(low[now],low[to]);
}
else if(flag[to]){
low[now]=min(low[now],low[to]);
}
}
if(dfn[now]==low[now]){
int x;cnt++;
do{
x=st.top();st.pop();flag[x]=0;siz[cnt]++;
belong[x]=cnt;
}while(x!=now);
}
}
long long n,m;
vector<long long>vec2[MX];
long long in[MX]={0};
signed main(){
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=m;i++){
long long x,y;scanf("%lld%lld",&x,&y);
vec[x].push_back(y);
}
for(long long i=1;i<=n;i++)if(!dfn[i]) tarjan(i);
long long sum=0,x=0,ls;
for(long long i=1;i<=n;i++){
for(auto j:vec[i]){
if(belong[i]==belong[j]) continue;
vec2[belong[i]].push_back(belong[j]);
// printf("check %lld %lld\n",belong[i],belong[j]);
in[belong[j]]++;
}
}
queue<long long>qu;long long ans=0;
for(long long i=1;i<=cnt;i++) if(!in[i])sum++,qu.push(i);
if(sum==1) ans+=siz[qu.front()];
while(!qu.empty()){
long long now=qu.front();qu.pop();
printf("now=%d %d\n",now,sum);
// if(sum==1&&x==0) ans+=siz[now];
sum--;
for(auto to:vec2[now]){
if(!--in[to]){
qu.push(to);
x++;ls=to;
}
}
if(!sum){
if(x==1) ans+=siz[ls],printf("ls=%d\n",ls);
sum=x,x=0,ls=0;
}
}
cout<<ans;
return 0;
}
/*
CCCCCCCCCCCCC AAA IIIIIIIIII CCCCCCCCCCCCC AAA IIIIIIIIII AAA
CCC::::::::::::C A:::A I::::::::I CCC::::::::::::C A:::A I::::::::I A:::A
CC:::::::::::::::C A:::::A I::::::::I CC:::::::::::::::C A:::::A I::::::::I A:::::A
C:::::CCCCCCCC::::C A:::::::A II::::::IIC:::::CCCCCCCC::::C A:::::::A II::::::II A:::::::A
C:::::C CCCCCC A:::::::::A I::::I C:::::C CCCCCC A:::::::::A I::::I A:::::::::A
C:::::C A:::::A:::::A I::::IC:::::C A:::::A:::::A I::::I A:::::A:::::A
C:::::C A:::::A A:::::A I::::IC:::::C A:::::A A:::::A I::::I A:::::A A:::::A
C:::::C A:::::A A:::::A I::::IC:::::C A:::::A A:::::A I::::I A:::::A A:::::A
C:::::C A:::::A A:::::A I::::IC:::::C A:::::A A:::::A I::::I A:::::A A:::::A
C:::::C A:::::AAAAAAAAA:::::A I::::IC:::::C A:::::AAAAAAAAA:::::A I::::I A:::::AAAAAAAAA:::::A
C:::::C A:::::::::::::::::::::A I::::IC:::::C A:::::::::::::::::::::A I::::I A:::::::::::::::::::::A
C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A I::::I C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A I::::I A:::::AAAAAAAAAAAAA:::::A
C:::::CCCCCCCC::::C A:::::A A:::::A II::::::IIC:::::CCCCCCCC::::C A:::::A A:::::A II::::::II A:::::A A:::::A
CC:::::::::::::::C A:::::A A:::::A I::::::::I CC:::::::::::::::C A:::::A A:::::A I::::::::I A:::::A A:::::A
CCC::::::::::::C A:::::A A:::::A I::::::::I CCC::::::::::::C A:::::A A:::::A I::::::::I A:::::A A:::::A
CCCCCCCCCCCCCAAAAAAA AAAAAAAIIIIIIIIII CCCCCCCCCCCCCAAAAAAA AAAAAAAIIIIIIIIIIAAAAAAA AAAAAAA
*/