1 #include <algorithm> 2 #include <cstdio> 3  4 using namespace std; 5  6 const int N(100015); 7 int n,m,v,u; 8 int edgesum,head[N]; 9 10 struct Edge11 {12 int from,to,next;13 Edge(int from=0,int to=0,int next=0) :14 from(from),to(to),next(next) {}15 }edge[N];16 int ins(int from,int to)17 {18 edge[++edgesum]=Edge(from,to,head[from]);19 return head[from]=edgesum;20 }21 22 int dfn[N],tim,low[N],vis[N];23 int Stack[N],top,instack[N];24 int col[N],colsum;25 26 void DFS(int now)27 {28 dfn[now]=low[now]=++tim; vis[now]=1;29 Stack[++top]=now; instack[now]=1;30 for(int i=head[now];i;i=edge[i].next)31  {32 int to=edge[i].to;33 if(instack[to]) low[i]=min(low[i],dfn[to]);34 else if(!vis[to])35 DFS(to),low[i]=min(low[i],low[to]);36  }37 if(low[now]==dfn[now])38  {39 colsum++;40 col[now]=colsum;41 for(;Stack[top]!=now;top--)42  {43 col[Stack[top]]=colsum;44 instack[Stack[top]]=0;45  }46 instack[now]=0;47 top--;48  }49 }50 51 int main()52 {53 scanf("%d%d",&n,&m);54 for(;m--;)55  {56 scanf("%d%d",&u,&v);57  ins(u,v);58  }59 for(int i=1;i<=n;i++)60 if(!vis[i]) DFS(i);61 return 0;62 }