Strongly Connected Components in Directed Graph

# 有向グラフにおける強連結成分分解

強連結：任意の2頂点対$(u, v)$について，$u$から$v$に至るパスと$v$から$u$に至るパスの双方が存在する
強連結成分：互いに強連結である頂点からなる頂点集合
強連結成分を計算するアルゴリズム
- 2回のDFSを行う
  - 【1】DFSを行って，頂点の帰りがけ順を求める
  - 【2】帰りがけ順上位から，元のグラフの辺の向きを逆転させたグラフ上でDFS

# 例題

https://atcoder.jp/contests/typical90/tasks/typical90_u

 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;

int N, M;

bool has_visited[1 << 18];
vector<int> G[1 << 18];
vector<int> RG[1 << 18];
vector<int> post_order;
long long cnt = 0;

void DFS(int node)
{
    has_visited[node] = true;
    for (int neighbor : G[node])
    {
        if (!has_visited[neighbor])
            DFS(neighbor);
    }
    post_order.push_back(node);
}

void RDFS(int node)
{
    has_visited[node] = true;
    cnt += 1;
    for (int neighbor : RG[node])
    {
        if (!has_visited[neighbor])
            RDFS(neighbor);
    }
}

int main()
{
    cin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        int A, B;
        cin >> A >> B;
        G[A].push_back(B);
        RG[B].push_back(A);
    }

    for (int i = 1; i <= N; i++)
        has_visited[i] = false;

    for (int node = 1; node <= N; node++)
    {
        if (!has_visited[node])
            DFS(node);
    }

    reverse(post_order.begin(), post_order.end());
    long long ans = 0;

    for (int i = 1; i <= N; i++)
        has_visited[i] = false;

    for (int node : post_order)
    {
        if (has_visited[node])
            continue;
        cnt = 0;
        RDFS(node);
        ans += cnt * (cnt - 1LL) / 2LL;
    }

    cout << ans << endl;

    return 0;
}