Tarjan算法

发表于 更新于 分类于 阅读次数：

两篇讲的比较好的文章: https://www.byvoid.com/blog/scc-tarjan/ https://www.byvoid.com/blog/biconnect/ 对于有向图和无向图，处理的大体方法一样的，不过概念不同 /*****************************************************************************/ tarjan在处理无向图的时候，遇到两点之间的有多条边的时候处理方法，和如何缩点，缩边代码：

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

void tarjan(int s,int pre)
{
    low[s]=dfn[s]=cnt++;
    vis[s]=true;
    int f=0;
    stk.push(s);
    //stk[stkCnt++]=s;
    for (int i=head[s];i!=-1;i=e[i].next)
    {
        int u=e[i].to;
        if (u==pre){f++; continue;}
        if (!dfn[u]){
            tarjan(u,s);
            low[s]=min(low[s],low[u]);
        }
        else if(vis[u])
            low[s]=min(low[s],dfn[u]);
    }
    if (f>=2) return;//这里用f处理了点与点之间如果遇到多条边的情况
    if (low[s]==dfn[s]){
            while (true)
            {
                //int t=stk[--stkCnt];//stk.pop();
                int t=stk.top();stk.pop();
                flag[t]=xx;
                vis[t]=false;
                if (t==s)
                {
                    break;
                }
            }
            xx++;
    }
}
vector *nMp;//[200010];
void build(int n)
{
   for (int i=0;i<n;i++)
   {//遍历所有的边，判断边的两边是不是在一个集合中的，不是就是割边
       int s,t;
       s=flag[e[i*2].from];
       t=flag[e[i*2].to];
       if (s!=t)
       {
           nMp[s].push_back(t);
           nMp[t].push_back(s);
       }
   }
}

  2013多校的第二场B题（hdu 4612） ac代码：

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <map>
using namespace std;
int n,m;
vector mp[200010];
struct edge
{
    int from;
    int to;
    int next;
};
edge e[2000020];
int head[200020];
stack stk;
//int stk[200010];
int stkCnt=0;
int flag[200010];
int xx;
int low[200010];
int dfn[200010];
bool vis[200010];
int cnt=0;
void tarjan(int s,int pre)
{
    low[s]=dfn[s]=cnt++;
    vis[s]=true;
    int f=0;
    stk.push(s);
    //stk[stkCnt++]=s;
    for (int i=head[s];i!=-1;i=e[i].next)
    {
        int u=e[i].to;
        if (u==pre){f++; continue;}
        if (!dfn[u]){
            tarjan(u,s);
            low[s]=min(low[s],low[u]);
        }
        else if(vis[u])
            low[s]=min(low[s],dfn[u]);
    }
    if (f>=2) return;
    if (low[s]==dfn[s]){
            while (true)
            {
                //int t=stk[--stkCnt];//stk.pop();
                int t=stk.top();stk.pop();
                flag[t]=xx;
                vis[t]=false;
                if (t==s)
                {
                    break;
                }
            }
            xx++;
    }
}
vector *nMp;//[200010];
void build(int n)
{
  /\*  for (int i=1;i<=n;i++)
   {
       for (int j=head[i];j!=-1;j=e[j].next)
       {
           if (flag[e[j].to]!=flag[i])
           {
               nMp[flag[i]].push_back(flag[e[j].to]);
               nMp[flag[e[j].to]].push_back(flag[i]);
           }
       }
   }*/
   for (int i=0;i<n;i++)
   {
       int s,t;
       s=flag[e[i*2].from];
       t=flag[e[i*2].to];
       if (s!=t)
       {
           nMp[s].push_back(t);
           nMp[t].push_back(s);
       }
   }
}

int ans,root;
void dfs(int now,int pre,int cnt)
{
    if (ans<=cnt)
    {
        ans=cnt;
        root=now;
    }
    for (int i=0;i<nMp[now].size();i++)
    {
        if (nMp[now][i]==pre) continue;
        dfs(nMp[now][i],now,cnt+1);
    }
}

int main()
{
//  int size = 256 << 20; // 256MB
//  char \*p = (char\*)malloc(size) + size;
//  \_\_asm\_\_("movl %0, %%esp\\n" :: "r"(p) );

while (scanf("%d%d",&n,&m)!=EOF)
{
    xx=0;
    memset(flag,-1,sizeof(flag));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(vis,false,sizeof(vis));
   // memset(stk,0,sizeof(stk));
    memset(head,-1,sizeof(head));
    stkCnt=0;
    for (int i=0;i<n+5;i++) mp[i].clear();
    if (m+n==0) break;
    for (int i=0;i<2*m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        e[i].to=b;
        e[i].from=a;
        e[i].next=head[a];
        head[a]=i;
        i++;
        e[i].to=a;
        e[i].from=b;
        e[i].next=head[b];
        head[b]=i;
    }
    tarjan(1,1);
    nMp=new vector[xx+10];
    build(m);
    ans=0;
    root=0;
    dfs(0,0,0);
    dfs(root,root,0);
    printf("%d\\n",xx-1-ans);
   // delete mp;
    delete nMp;
}
    return 0;
}