rt,52pts,WA了六个点 代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,head[N],tot;
struct Edge{
int to,nxt;
}edge[N];
int dfn[N],low[N],stk[N],top;
bool ins[N];
int cnt,idx,siz[N],scc[N];
inline int read(){
int s=0,f=1;char ch=getchar();
while(ch<'0' or ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' and ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
return f*s;
}
inline void write(int num){
if(num<0)putchar('-');
if(num>9)write(num/10);
putchar(num%10+48);
}
inline void add(int u,int v){
edge[++tot].to=v;
edge[cnt].nxt=head[u];
head[u]=tot;
}
inline void tarjan(int u){
low[u]=dfn[u]=++cnt;
ins[stk[++top]=u]=true;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(ins[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
int v;idx++;
do{
v=stk[top--];
scc[v]=idx;
siz[idx]++;
}while(v!=u);
}
}
int main(){
n=read(),m=read();
for(int i=1,u,v;i<=m;i++){
u=read(),v=read();
add(u,v);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
int ans=0;
for(int i=1;i<=idx;i++)
ans+=siz[i]>1;
write(ans);
return 0;
}