Tarjan

Tarjan基于深搜,是一种离线算法

强连通分量

连通块（有向图）

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
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1e6 + 5;
stack<int> k;
vector<int> mp[M], ans[M];
bool instack[M] = {0};
int dfn[M] = {0}, low[M] = {0}, cnt = 0, t = 0;
void tarjan(int x)
{
   dfn[x] = low[x] = ++cnt;
   k.push(x);
   instack[x] = true;
   for (int i = 0; i < mp[x].size(); i++)
   {
      if (!dfn[mp[x][i]])
      {
         tarjan(mp[x][i]);
         low[x] = min(low[x], low[mp[x][i]]);
      }
      else if (instack[mp[x][i]])
      {
         low[x] = min(low[x], dfn[mp[x][i]]); // find root
      }
   }
   if (low[x] == dfn[x]) // get way
   {
      int node;
      do
      {
         node = k.top();
         k.pop();
         instack[node] = false;
         ans[t].push_back(node);
      } while (node != x);
      t++;
   }
}
int main()
{
   int n, m;
   cin >> n >> m;
   for (int i = 0; i < m; i++)
   {
      int a, b;
      cin >> a >> b;
      mp[a].push_back(b);
   }
   tarjan(1);
   for (int i = 0; i < t; i++)
   {
      cout << "SCG " << i << ":";
      for (int j = 0; j < ans[i].size(); j++)
      {
         cout << " " << ans[i][j];
      }
      cout << endl;
   }
   return 0;
}

缩点（有向图）

P3387 【模板】缩点 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

采用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
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1e4 + 5;
struct book
{
    int from = -1, to = -1;
};
int n, m, sum[M], fa[M], ru[M] = {0}, mmax = -1;
bool v[M] = {false};
vector<int> mp[M], nw[M];
int low[M] = {0}, dfn[M] = {0}, cnt = 0;
stack<int> st;
int ans[M] = {0};
void init()
{
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
    }
}
void tarjan(int x)
{
    dfn[x] = low[x] = ++cnt;
    v[x] = true;
    st.push(x);
    for (int next : mp[x])
    {
        if (!dfn[next])
        {
            tarjan(next);
            low[x] = min(low[x], low[next]);
        }
        else if (v[next])
        {
            low[x] = min(dfn[next], low[x]);
        }
    }
    if (low[x] == dfn[x])
    {
        int node;
        do
        {
            node = st.top();
            st.pop();
            v[node] = false;
            fa[node] = x;
            if (node == x)
            {
                break;
            }
            sum[x] += sum[node];
        } while (1);
    }
}
vector<book> way;
int get()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        if (!ru[i] && fa[i] == i)
        {
            q.push(i);
            ans[i] = sum[i];
        }
    }
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int next : nw[u])
        {
            ru[next]--;
            ans[next] = max(ans[next], ans[u] + sum[next]);
            if (!ru[next])
            {
                q.push(next);
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        mmax = max(ans[i], mmax);
    }
    return mmax;
}
int main()
{
    cin >> n >> m;
    init();
    for (int i = 1; i <= n; i++)
    {
        cin >> sum[i];
    }
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        mp[a].push_back(b);
        way.push_back({a, b});
    }
    for (int i = 1; i <= n; i++)
    {
        if (dfn[i])
        {
            continue;
        }
        cnt = 0;
        tarjan(i);
    }
    for (int i = 0; i < m; i++)
    {
        int x = fa[way[i].from], y = fa[way[i].to];
        if (x != y)
        {
            nw[x].push_back(y);
            ru[y]++;
        }
    }
    cout << get();
    return 0;
}

割点（无向图）

P3388 【模板】割点（割顶） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1e5 + 5;
int n, m, cnt = 0;
int dfn[M] = {0}, low[M] = {0};
vector<int> mp[M];
bool v[M] = {false};
void tarjan(int x, int fa)
{
    int t = 0;
    dfn[x] = low[x] = ++cnt;
    for (int next : mp[x])
    {
        if (!dfn[next])
        {
            tarjan(next, fa);
            if (low[next] >= dfn[x] && x != fa)
            {
                v[x] = true;
            }
            if (x == fa)
            {
                t++;
            }
            low[x] = min(low[next], low[x]);
        }
        low[x] = min(dfn[next], low[x]);
    }
    if (t > 1 && fa == x)
    {
        v[x] = true;
    }
}
int main()
{
    cin >> n >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    for (int i = 1; i <= n; i++)
    {
        if (dfn[i])
        {
            continue;
        }
        cnt = 0;
        tarjan(i, i);
    }
    vector<int> ans;
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        if (v[i])
        {
            ans.push_back(i);
            sum++;
        }
    }
    cout << sum << endl;
    for (int i = 0; i < ans.size(); i++)
    {
        if (i)
        {
            cout << " ";
        }
        cout << ans[i];
    }
    return 0;
}

桥（无向图）

P1656 炸铁路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dfn[205], low[205], cnt = 0;
int n, m;
vector<int> mp[205];
struct book
{
    int a, b;
};
vector<book> ans;
void tarjan(int x, int fa)
{
    dfn[x] = low[x] = ++cnt;
    for (int u : mp[x])
    {
        if (!dfn[u])
        {
            tarjan(u, x);
            if (low[u] > dfn[x])
            {
                ans.push_back({x, u});
            }
            low[x] = min(low[u], low[x]);
        }
        else if (u != fa)
        {
            low[x] = min(dfn[u], low[x]);
        }
    }
}
bool cmp(book a, book b)
{
    if (a.a == b.a)
    {
        return a.b < b.b;
    }
    return a.a < b.a;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    for (int i = 1; i <= n; i++)
    {
        sort(mp[i].begin(), mp[i].end());
    }
    for (int i = 1; i <= n; i++)
    {
        if (dfn[i])
        {
            continue;
        }
        tarjan(i, i);
    }
    sort(ans.begin(), ans.end(), cmp);
    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i].a << " " << ans[i].b << endl;
    }
    // for (int i = 0; i < t; i++)
    // {
    //     for (int u : h[i])
    //     {
    //         cout << u << " ";
    //     }
    //     cout << endl;
    // }
    return 0;
}

LCA（最近公共祖先）

P3379 【模板】最近公共祖先（LCA） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Tarjan+链式前向星+并查集+map映射

如果不用链式前向星会超时

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pr pair<int, int>
#define mk(a, b) make_pair(a, b)
const int M = 500005;
const int MX = 1e6 + 5;
int tot = 0, lk = 0;
int low[M] = {0}, dfn[M] = {0}, cnt = 0;
int n, m, s;
int head[M], hd[M];
int A[M] = {0};
int B[M] = {0};
map<int, int> ans[M];
struct book
{
    int to, next = 0;
} node[MX], link[MX];
void add(int u, int v)
{
    node[++tot] = {v, head[u]};
    head[u] = tot;
}
void addwy(int u, int v)
{
    link[++lk] = {v, hd[u]};
    hd[u] = lk;
}
bool v[M] = {false};
int fa[M] = {0};
int fd(int x)
{
    return fa[x] = fa[x] == x ? x : fd(fa[x]);
}
void un(int x, int y)
{
    fa[fd(y)] = fd(x);
}
void tarjan(int x)
{
    v[x] = true;
    fa[x] = x;
    for (int i = head[x]; i; i = node[i].next)
    {
        int y = node[i].to;
        if (v[y])
        {
            continue;
        }
        tarjan(y);
        un(x, y);
    }
    for (int i = hd[x]; i; i = link[i].next)
    {
        int y = link[i].to;
        if (v[y])
        {
            // pr t1, t2;
            // t1 = mk(x, y);
            // t2 = mk(y, x);
            int root = fd(y);
            // ans[t1] = ans[t2] = root;
            ans[x][y] = ans[y][x] = root;
        }
    }
}
int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    cin >> n >> m >> s;
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    for (int i = 0; i < m; i++)
    {
        cin >> A[i] >> B[i];
        addwy(A[i], B[i]);
        addwy(B[i], A[i]);
    }
    tarjan(s);
    // for (int i = 1; i <= n; i++)
    // {
    //     cout << i << " : ";
    //     for (int j = head[i]; j; j = node[j].next)
    //     {
    //         cout << node[j].to << " ";
    //     }
    //     cout << endl;
    // }
    for (int i = 0; i < m; i++)
    {
        // cout << ans[mk(A[i], B[i])] << endl;
        cout << ans[A[i]][B[i]] << endl;
    }
    return 0;
}