#include<cstdio>
#include<iostream>
#include<bitset>
#include<cstring>
#include<queue>
#include<algorithm>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
using namespace std;
const int MAXN=30001;
inline int read()
{
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
struct node
{
int u,v,nxt;
}edge[MAXN*10];
int head[MAXN],num=1;
inline void AddEdge(int x,int y)
{
edge[num].u=x;
edge[num].v=y;
edge[num].nxt=head[x];
head[x]=num++;
}
int VisitTime[MAXN];//i是第几个入队的
int InputTime[MAXN];//第i个入队的是谁
int inder[MAXN];
bitset<MAXN>can[MAXN];//联通性
int N,M;
int to[MAXN];
int comp(const int &a,const int &b)
{
return VisitTime[a]<VisitTime[b];
}
void Topsort()
{
queue<int>q;
for(int i=1;i<=N;i++)
if(inder[i]==0) q.push(i);
int tot=0;
while(q.size()!=0)
{
int p=q.front();q.pop();
InputTime[++tot]=p;
VisitTime[p]=tot;
for(int i=head[p];i!=-1;i=edge[i].nxt)
{
inder[edge[i].v]--;
if(inder[edge[i].v]==0)
q.push(edge[i].v);
}
}
int ans=0;
for(int i=N;i>=1;i--)
{
int x=InputTime[i],tot=0;
can[x][x]=1;
for(int j=head[x];j!=-1;j=edge[j].nxt)
to[++tot]=edge[j].v;
sort(to+1,to+tot+1,comp);
for(int j=1;j<=tot;j++)
{
if(can[x][to[j]]) ans++;
else can[x]|=can[to[j]];
}
}
printf("%d",ans);
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#endif
memset(head,-1,sizeof(head));
N=read(),M=read();
for(int i=1;i<=M;i++)
{
int x=read(),y=read();
AddEdge(x,y);
inder[y]++;
}
Topsort();
return 0;
}
网友评论