Tarjan缩点【模板】

 1 #include <algorithm>
 2 #include <cstdio>
 3 #include <map>
 4 
 5 using namespace std;
 6 
 7 const int N(100015);
 8 map<int,bool>Map[N];
 9 int n,m,v,u;
10 int edgesum,head[N];
11 int edgesum2,head2[N];
12 
13 struct Edge
14 {
15     int from,to,next;
16     Edge(int from=0,int to=0,int next=0) :
17         from(from),to(to),next(next) {}
18 }edge[N],edge2[N];
19 int ins(int from,int to)
20 {
21     edge[++edgesum]=Edge(from,to,head[from]);
22     return head[from]=edgesum;
23 }
24 
25 int ins2(int from,int to)
26 {
27     edge2[++edgesum2]=Edge(from,to,head2[from]);
28     return head2[from]=edgesum2;
29 }
30 
31 int dfn[N],tim,low[N],vis[N];
32 int Stack[N],top,instack[N];
33 int col[N],colsum;
34 
35 void DFS(int now)
36 {
37     dfn[now]=low[now]=++tim; vis[now]=1;
38     Stack[++top]=now; instack[now]=1;
39     for(int i=head[now];i;i=edge[i].next)
40     {
41         int to=edge[i].to;
42         if(instack[to]) low[i]=min(low[i],dfn[to]);
43         else if(!vis[to])
44                 DFS(to),low[i]=min(low[i],low[to]);
45     }
46     if(low[now]==dfn[now])
47     {
48         colsum++;
49         col[now]=colsum;
50         for(;Stack[top]!=now;top--)
51         {
52             col[Stack[top]]=colsum;
53             instack[Stack[top]]=0;
54         }
55         instack[now]=0;
56         top--;
57     }
58 }
59 
60 int main()
61 {
62     scanf("%d%d",&n,&m);
63     for(;m--;)
64     {
65         scanf("%d%d",&u,&v);
66         ins(u,v);
67     }
68     for(int i=1;i<=n;i++)
69         if(!vis[i]) DFS(i);
70     for(int i=1;i<=n;i++)
71       for(int u=head[i];u;u=edge[i].next)
72       {
73           int v=edge[i].to;
74             if(col[i]!=col[v])
75                 if(Map[col[i]].find(col[v])==Map[col[i]].end())
76                 {
77                     Map[col[i]][col[v]]=1;
78                     ins2(col[i],col[v]);
79             }
80       }
81     return 0;
82 }
——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。