连通分量

P3387【模板】缩点 
 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
namespace LCL
{
    constexpr int MAXN = 1e4 + 10, MAXV = MAXN << 2, P = 998244353;
    auto min = [](auto x, auto y) { return x < y ? x : y; };
    auto max = [](auto x, auto y) { return x < y ? y : x; };
    auto tadd = [](auto x, auto y) { return add(x, y); };
    auto cadd = [](auto x, auto y) { return x + min(y, inf - x); };
    auto qmul = [](auto x, auto y) { return (x = (ull)x * y - (ull)((ld)x / P * y) * P) < 0 ? x + P : x; };
    auto cmod = [](auto x) { return (x %= P) < 0 ? x + P : x; };
    auto abs = [](auto x) { return x < 0 ? -x : x; };
    auto lowb = [](auto x) { return x & (-x); };
    int n, m, a[MAXN], w[MAXN], dfc, dfn[MAXN], low[MAXN], scc[MAXN], sidx, dp[MAXN], stk[MAXN], tp;
    vi e[MAXN], g[MAXN];
    bitset<MAXN> vis;
    void dfs(int u)
    {
        if (vis[u]) return;
        for (int v : g[u]) dfs(v), chkmx(dp[u], dp[v]);
        dp[u] += w[u], vis[u] = 1;
    }
    void tarjan(int u)
    {
        dfn[u] = low[u] = ++dfc, stk[++tp] = u;
        for (int v : e[u])
            if (!dfn[v])
                tarjan(v), chkmn(low[u], low[v]);
            else if (!scc[v])
                chkmn(low[u], dfn[v]);
        if (low[u] == dfn[u])
        {
            sidx++;
            do scc[stk[tp]] = sidx, w[sidx] += a[stk[tp]];
            while (stk[tp--] ^ u);
        }
    }
    void main()
    {
        cin >> n >> m;
        rep(i, 1, n) cin >> a[i];
        rep(i, 1, m, u, v) cin >> u >> v, e[u].eb(v);
        rep(i, 1, n) if (!dfn[i]) tarjan(i);
        rep(u, 1, n) for (int v : e[u]) if (scc[u] ^ scc[v]) g[scc[u]].eb(scc[v]);
        rep(i, 1, sidx) dfs(i);
        cout << *max_element(dp + 1, dp + 1 + sidx);
    }
} // namespace LCL
P8436【模板】边双连通分量 
 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
namespace LCL
{
    constexpr int MAXN = 5e5 + 10, MAXM = 2e6 + 10, MAXV = MAXN << 2, P = 998244353;
    auto min = [](auto x, auto y) { return x < y ? x : y; };
    auto max = [](auto x, auto y) { return x < y ? y : x; };
    auto tadd = [](auto x, auto y) { return add(x, y); };
    auto cadd = [](auto x, auto y) { return x + min(y, inf - x); };
    auto qmul = [](auto x, auto y) { return (x = (ull)x * y - (ull)((ld)x / P * y) * P) < 0 ? x + P : x; };
    auto cmod = [](auto x) { return (x %= P) < 0 ? x + P : x; };
    auto abs = [](auto x) { return x < 0 ? -x : x; };
    auto lowb = [](auto x) { return x & (-x); };
    int n, m, dfc, low[MAXN], dfn[MAXN], stk[MAXN], tp;
    vii bccs;
    bitset<MAXN> inq;
#define go(u, i) for (int i = head[u]; i; i = e[i].nxt)
    struct edge
    {
        int v, nxt;
    } e[MAXM << 1];
    int head[MAXN];
    inline void addedge(int u, int v)
    {
        static int edgecnt = 1;
        e[++edgecnt] = {v, head[u]};
        head[u] = edgecnt;
    }
    inline void adde(int u, int v) { addedge(u, v), addedge(v, u); }
    void tarjan(int u, int fr)
    {
        low[u] = dfn[u] = ++dfc, stk[++tp] = u, inq[u] = 1;
        go(u, i) if (fr ^ i && fr ^ i ^ 1)
        {
            int v = e[i].v;
            if (!dfn[v])
                tarjan(v, i), chkmn(low[u], low[v]);
            else if (inq[v])
                chkmn(low[u], dfn[v]);
        }
        if (low[u] == dfn[u])
        {
            vi bcc;
            do bcc.eb(stk[tp]), inq[stk[tp]] = 0;
            while (stk[tp--] ^ u);
            bccs.eb(move(bcc));
        }
    }
    void main()
    {
        cin >> n >> m;
        rep(i, 1, m, u, v) cin >> u >> v, adde(u, v);
        rep(i, 1, n) if (!dfn[i]) tarjan(i, 0);
        cout << SZ(bccs) << endl;
        for (vi &bcc : bccs)
        {
            cout << SZ(bcc) << " ";
            for (int &x : bcc) cout << x << " ";
            cout << endl;
        }
    }
} // namespace LCL
P8435【模板】点双连通分量 
 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
namespace LCL
{
    constexpr int MAXN = 5e5 + 10, MAXV = MAXN << 2, P = 998244353;
    auto min = [](auto x, auto y) { return x < y ? x : y; };
    auto max = [](auto x, auto y) { return x < y ? y : x; };
    auto tadd = [](auto x, auto y) { return add(x, y); };
    auto cadd = [](auto x, auto y) { return x + min(y, inf - x); };
    auto qmul = [](auto x, auto y) { return (x = (ull)x * y - (ull)((ld)x / P * y) * P) < 0 ? x + P : x; };
    auto cmod = [](auto x) { return (x %= P) < 0 ? x + P : x; };
    auto abs = [](auto x) { return x < 0 ? -x : x; };
    auto lowb = [](auto x) { return x & (-x); };
    int n, m, dfc, low[MAXN], dfn[MAXN], tp, stk[MAXN];
    vii dccs;
    vi e[MAXN];
    void tarjan(int u)
    {
        stk[++tp] = u, low[u] = dfn[u] = ++dfc;
        for (int v : e[u])
            if (!dfn[v])
            {
                tarjan(v), chkmn(low[u], low[v]);
                if (dfn[u] <= low[v])
                {
                    vi dcc;
                    do dcc.eb(stk[tp]);
                    while (stk[tp--] ^ v);
                    dcc.eb(u), dccs.eb(move(dcc));
                }
            }
            else
                chkmn(low[u], dfn[v]);
    }
    void main()
    {
        cin >> n >> m;
        rep(i, 1, m, u, v)
        {
            cin >> u >> v;
            if (u ^ v) e[u].eb(v), e[v].eb(u);
        }
        rep(i, 1, n) if (!dfn[i])
        {
            if (e[i].empty())
                dccs.eb(vi{i});
            else
                tp = 0, tarjan(i);
        }
        cout << SZ(dccs) << endl;
        for (vi &dcc : dccs)
        {
            cout << SZ(dcc) << " ";
            for (int &x : dcc) cout << x << " ";
            cout << endl;
        }
    }
} // namespace LCL
P3388【模板】割点（割顶） 
 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
namespace LCL
{
    constexpr int MAXN = 2e4 + 10, MAXV = MAXN << 2, P = 998244353;
    auto min = [](auto x, auto y) { return x < y ? x : y; };
    auto max = [](auto x, auto y) { return x < y ? y : x; };
    auto tadd = [](auto x, auto y) { return add(x, y); };
    auto cadd = [](auto x, auto y) { return x + min(y, inf - x); };
    auto qmul = [](auto x, auto y) { return (x = (ull)x * y - (ull)((ld)x / P * y) * P) < 0 ? x + P : x; };
    auto cmod = [](auto x) { return (x %= P) < 0 ? x + P : x; };
    auto abs = [](auto x) { return x < 0 ? -x : x; };
    auto lowb = [](auto x) { return x & (-x); };
    int n, m, dfc, low[MAXN], dfn[MAXN];
    vi e[MAXN];
    bitset<MAXN> cut;
    void tarjan(int u, int f)
    {
        dfn[u] = low[u] = ++dfc;
        int ch = 0;
        for (int v : e[u])
            if (!dfn[v])
            {
                ch++, tarjan(v, u), chkmn(low[u], low[v]);
                if (f && dfn[u] <= low[v]) cut[u] = 1;
            }
            else if (v ^ f)
                chkmn(low[u], dfn[v]);
        if (!f && ch >= 2) cut[u] = 1;
    }
    void main()
    {
        cin >> n >> m;
        rep(i, 1, m, u, v) cin >> u >> v, e[u].eb(v), e[v].eb(u);
        rep(i, 1, n) if (!dfn[i]) tarjan(i, 0);
        cout << cut.count() << endl;
        rep(i, 1, n) if (cut[i]) cout << i << " ";
    }
} // namespace LCL