1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
const int N = 1e5+10;
struct node{
int v,next;
}edge[N];
int dfn[N],low[N],st[N];
int head[N],vis[N],cnt,tot,ans,index_;
void add(int u,int v){
edge[cnt].next=head[u];
edge[cnt].v=v;
head[u]=cnt++;
}
void tarjan(int x){
dfn[x]=low[x]=++tot;
st[++index_]=x;
vis[x]=1;
for(int i=head[x];i!=-1;i=edge[i].next){
if(!dfn[edge[i].v])
{
tarjan(edge[i].v);
low[x]=min(low[x],low[edge[i].v]);
}else if(vis[edge[i].v]){
low[x]=min(low[x],dfn[edge[i].v]);
}
}
if(low[x]==dfn[x]){
int cnt = 0;
do{
vis[st[index_]]=0;
index_--;
cnt++;
}while(x!=st[index_+1]);
if(cnt>1)
ans++;
}
return ;
}
int main(){
int n,m;
memset(head,-1,sizeof(head));
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
int u,v;
scanf("%d %d",&u,&v);
add(u,v);
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
printf("%d\n",ans);
}
|