缩点

每个环都缩成一个点，把有环图变为无环图

变量

\(scc[u]\)，节点 \(u\) 所在环的编号

例题

Luogu P3387 【模板】缩点

题目描述

给定一个 \(n\) 个点 \(m\) 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入格式

第一行两个正整数 \(n,m\)

第二行 \(n\) 个整数，其中第 \(i\) 个数 \(a_i\) 表示点 \(i\) 的点权.

第三至 \(m + 2\) 行，每行两个整数 \(u,v\)，表示一条 \(u→υ\) 的有向边。

输出格式

共一行，最大的点权之和。

数据范围

\(1 \leq n < 10^4, \ 1 \leq m \leq 10^5, \ 0 \leq a_i < 10^3\)

code:

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
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, m;
int w[N];
int f[N];
vector<int> h[N], nh[N];
int dfn[N], low[N], tot;
int stk[N], instk[N], top;
int scc[N], sz[N], cnt;

void tarjan(int u)
{
    dfn[u] = low[u] = ++tot;
    stk[++top] = u, instk[u] = 1;
    for (int i = 0; i < h[u].size(); i++)
    {
        int v = h[u][i];
        if (!dfn[v]) 
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (instk[v]) low[u] = min(low[u], dfn[v]);
    }

    if (dfn[u] == low[u])
    {
        cnt++;
        int v;
        do 
        {
            v = stk[top--];
            instk[v] = 0;
            scc[v] = cnt;
            sz[cnt] += w[v];
        } while (u != v);
    }
}

void dfs(int u)
{
    for (int i = 0; i < nh[u].size(); i++)
    {
        int v = nh[u][i];
        if (!f[v]) dfs(v);
        f[u] = max(f[u], f[v]); 
    }
    f[u] += sz[u];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        h[a].push_back(b);
    }

    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
            
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < h[i].size(); j++)
        {
            int u = scc[i], v = scc[h[i][j]];
            if (u != v) nh[u].push_back(v);	
        }

    int res = 0;
    for (int i = 1; i <= cnt; i++)
        if (!f[i])
        {
            dfs(i);
            res = max(res, f[i]);
        }

    cout << res << endl;

    return 0;
}

Luogu P2812 校园网络

题目描述

共有 \(n\) 所学校 \((1<n<10000)\) 已知他们实现设计好的网络共 \(m\) 条线路，为了保证高速，网络是单向的。现在请你告诉他们至少选几所学校作为共享软件的母机，能使每所学校都可以用上。再告诉他们至少要添加几条线路能使任意一所学校作为母机都可以使别的学校使用上软件。

输入格式

第一行一个正整数 \(n\)。

接下来 \(n\) 行每行有若干个整数，用空格隔开。

第 \(i+ 1\) 行，每行输入若干个非零整数，表示从 \(i\) 到 \(x\) 有一条线路。以 \(0\) 作为结束标志。

输出格式

第一行一个整数，表示至少选几所学校作为共享软件的母机，能使每所学校都可以用上。

第二行一个整数，表示至少要添加几条线路能使任意一所学校作为母机都可以使别的学校使用上软件。

数据范围

\(1 \leq n < 10^4, \ 1 \leq\) 边数 \(\leq 5 \times 10^4\)

code:

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
#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

int n;
vector<int> h[N];
int dfn[N], low[N], tot;
int stk[N], instk[N], top;
int scc[N], sz[N], cnt;
int in[N], out[N];

void tarjan(int u)
{
    dfn[u] = low[u] = ++tot;
    stk[++top] = u, instk[u] = 1;
    for (int i = 0; i < h[u].size(); i++)
    {
        int v = h[u][i];
        if (!dfn[v]) 
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (instk[v]) low[u] = min(low[u], dfn[v]);
    }

    if (dfn[u] == low[u])
    {
        cnt++;
        int v;
        do 
        {
            v = stk[top--];
            instk[v] = 0;
            scc[v] = cnt;
            sz[cnt]++;
        } while (u != v);
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        while (cin >> x, x) h[i].push_back(x);
    }

    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
            
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < h[i].size(); j++)
            if (scc[h[i][j]] != scc[i])
                in[scc[h[i][j]]]++, out[scc[i]]++;
            
    int r1 = 0, r2 = 0;
    for (int i = 1; i <= cnt; i++)
    {
        if (!in[i]) r1++;
        if (!out[i]) r2++;
    }

    cout << r1 << endl;
    if (cnt == 1) cout << 0 << endl;
    else cout << max(r1, r2) << endl;

    return 0;
}