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 }