22.5 Strongly connected component

문제: https://www.acmicpc.net/problem/2150

Kosaraju's algorithm

실제 책에 소개되는 알고리즘

참고 : https://jason9319.tistory.com/98

$O(V+E)$ 

 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
Graph STRONGLY_CONNECTED_COMPONENTS(const Graph &G)
{
    const int v = G.size()-1;

    Graph SSC;
    std::stack<int> DFSf; // DFS pop 순서대로 들어가있다.
    std::vector<bool> visit(v+2 ,false);
    for (int i = 1; i <= v; i++) {
        if (visit[i] != true)
            DFS(G, i, DFSf,visit); //DFS순회 순서를 S에 저장한다.
    }

    Graph TG(v + 1, (std::vector<int>()));//G^T
    for (int i = 1; i <= v; i++)
    {
        for (int j : G[i])
        {
            TG[j].push_back(i);
        }
    }

    visit.assign(v+1,false);
    for (int i = 0; i < v; i++)
    {
        if (visit[DFSf.top()] != true)
        {
            SSC.push_back(std::vector<int>());
            TDFS(TG, DFSf.top(), SSC[SSC.size()-1],visit);
            ///SSC_n++;
        }
        DFSf.pop();
    }
    return SSC;
}

with for 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void DFS(const Graph &G, int x, std::stack<int>& DFSf , std::vector<bool> &visit)
{
    visit[x] = true;
    std::stack<int> sub_s;
    sub_s.push(x);
    while (!sub_s.empty())
    {
        int y = sub_s.top();
        for (std::size_t i = 0; i < G[y].size(); i++)
        {
            int next = G[y][i];
            if (visit[next] != true)
            {
                visit[next] = true;
                sub_s.push(next);
                i = -1;
                y = sub_s.top();
            }
        }
        DFSf.push(sub_s.top());//기존 DFS와 차이 STACK에 종료 순서 저장
        sub_s.pop();
    }
}

with recursion 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void DFS(const Graph& G, int x, std::stack<int>& DFSf, std::vector<bool>& visit)
{
    visit[x] = true;

    //std::cout << x << ' '; // 순회출력

    for (int next : G[x])
    {
        if (visit[next] != true)
        {
            DFS(G, next, DFSf,visit);
        }
    }
    DFSf.push(x);//기존 DFS와 차이 STACK에 종료 순서 저장
}
with for 
 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
void TDFS(Graph &TG, int x,std::vector<int> &SSC, std::vector<bool> &visit)//G^T탐색
{
    visit[x] = true;

    std::stack<int> sub_s;
    sub_s.push(x);

    //std::cout << sub_s.top() << ' '; // 순회출력

    while (!sub_s.empty())
    {
        int y = sub_s.top();
        for (std::size_t i = 0; i < TG[y].size(); i++)
        {
            int next = TG[y][i];
            if (visit[next] != true)
            {
                visit[next] = true;
                sub_s.push(next);

                //std::cout << sub_s.top() << ' '; // 순회출력

                i = -1;
                y = sub_s.top();
            }

        }
        SSC.push_back(sub_s.top());
        sub_s.pop();
    }
}
with recursion 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
//SSC[] 1D vector
void TDFS(Graph& TG, int x, std::vector<int>& SSC, std::vector<bool>& visit)
{
    visit[x] = true;
    //std::cout << x << ' '; // 순회출력
    for (int next : TG[x])
    {
        if (visit[next] != true)
        {
            TDFS(TG, next, SSC,visit);
        }
    }
    SSC.push_back(x);
}

+ Tarjan's alg

$O(V+E)$

참고 : https://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221236952158&parentCategoryNo=&categoryNo=128&viewDate=&isShowPopularPosts=false&from=postView

해당 코드를 토대로 매개변수를 옮김

 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
// 자신의 결과값을 리턴하는 DFS 함수
int DFS(int curr, vector<vector<int>>& SCC,
    vector<bool>& finished, stack<int>& S, vector<vector<int>>& adj, vector<int>& dfsn, int &cnt)
{
    dfsn[curr] = ++cnt; // dfsn 결정
    S.push(curr);       // 스택에 자신을 push

    // 자신의 dfsn, 자식들의 결과나 dfsn 중 가장 작은 번호를 result에 저장
    int result = dfsn[curr];
    for (int next : adj[curr])
    {
        // 아직 방문하지 않은 이웃
        if (dfsn[next] == 0)
        {
            result = min(result, DFS(next, SCC, finished, S, adj, dfsn, cnt));
        }
        // 방문은 했으나 아직 SCC로 추출되지는 않은 이웃
        else if (!finished[next])
        {
            result = min(result, dfsn[next]);
        }
    }

    // 자신, 자신의 자손들이 도달 가능한 제일 높은 정점이 자신일 경우 SCC 추출
    if (result == dfsn[curr])
    {
        vector<int> currSCC;
        // 스택에서 자신이 나올 때까지 pop
        while (1)
        {
            int t = S.top();
            S.pop();
            currSCC.push_back(t);
            finished[t] = true;
            //sn[t] = SN;
            if (t == curr)
            {
                break;
            }
        }
        // 출력을 위해 원소 정렬
        sort(currSCC.begin(), currSCC.end());
        // SCC 추출
        SCC.push_back(currSCC);
    }
    return result;
}

std::vector<vector<int>> TARJAN_ALG(std::vector<vector<int>>& adj)
{
    const int V = adj.size();

    std::vector<int>  dfsn(V + 1);
    std::vector<vector<int>> SCC;
    std::stack<int> S;
    std::vector<bool> finished(V + 1); // SCC 분리가 끝난 정점만 true
    int cnt = 0 ;

    for (int i = 0; i < V - 1 ; i++)
    {
        if (dfsn[i] == 0)
        {
            DFS(i, SCC, finished, S, adj, dfsn,cnt);
        }
    }
    return SCC;
}