SCC - kosaraju

SCC ( Strongly Connected Component )

 

강한 연결 요소, 집합 내에서 서로 왕복 가능한 최대 집합의 크기

---

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

2150번: Strongly Connected Component

 

1. 방향 그래프, 역방향 그래프, 스택을 준비한다.
2. 방향 그래프를 사용하여 dfs를 수행하고, 끝나는 순서대로 스택에 push한다. (단, 모든 정점에 대해서 수행)
3. 스택을 비울 때까지 pop을 하면서, 역방향 그래프를 사용하여 dfs를 수행하고 모든 정점들을 같은 SCC로 묶는다.

[ JAVA ]

class Main {
    static ArrayList<Integer> graph[];
    static ArrayList<Integer> reverse[];
    static boolean visited[];
    static Stack<Integer> st = new Stack<>();
    // Result
    static ArrayList<ArrayList<Integer>> a = new ArrayList<>();

    static void dfs(int now) {
        for (int a : graph[now]) {
            if (visited[a] == false) {
                visited[a] = true;
                dfs(a);
            }
        }
        st.push(now);
    }

    static void rdfs(int base, ArrayList<Integer> temp) {
        temp.add(base);
        for (int a : reverse[base]) {
            if (!visited[a]) {
                visited[a] = true;
                rdfs(a, temp);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken());
        int m = Integer.parseInt(stk.nextToken());

        graph = new ArrayList[n + 1];
        reverse = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
            reverse[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(stk.nextToken());
            int to = Integer.parseInt(stk.nextToken());
            graph[from].add(to);
            reverse[to].add(from);
        }

        // stack
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(i);
            }
        }

        Arrays.fill(visited, false);

        while (!st.isEmpty()) {
            int base = st.pop();
            if (!visited[base]) {
                visited[base] = true;
                ArrayList<Integer> temp = new ArrayList<>();
                rdfs(base, temp);
                Collections.sort(temp);
                temp.add(-1);
                a.add(temp);
            }
        }

        Collections.sort(a, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                return Integer.compare(o1.get(0), o2.get(0));
            }
        });

        StringBuilder sb = new StringBuilder();
        sb.append(a.size()).append("\n");
        for (int i = 0; i < a.size(); i++) {
            int size = a.get(i).size();
            for (int j = 0; j < size; j++) {
                sb.append(a.get(i).get(j)).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);

        br.close();
    }
}

 

[ C++ ]

#include <stdio.h>
#include <memory.h>
#include <algorithm>
#include <vector>
using namespace std;

typedef vector<int> vi;
const int v_ = 1e4 + 1;

int v, e, cnt, pos, stk[v_];
bool vst[v_];
vi gp1[v_], gp2[v_];
vector<vi> res;

void dfs(int now)
{
    vst[now] = true;
    for (int nxt : gp1[now])
        if (!vst[nxt])
            dfs(nxt);
    stk[pos++] = now;
}

void scc(int now)
{
    vst[now] = true;
    res[cnt].push_back(now);
    for (int nxt : gp2[now])
        if (!vst[nxt])
            scc(nxt);
}

int main()
{
    int i;
    scanf("%d %d", &v, &e);
    for (i = 1; i <= e; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        gp1[a].push_back(b);
        gp2[b].push_back(a);
    }

    for (i = 1; i <= v; i++)
        if (!vst[i])
            dfs(i);

    memset(vst, 0, sizeof(vst));
    while (pos)
    {
        int top = stk[--pos];
        if (vst[top])
            continue;
        res.push_back(vi());
        scc(top);
        cnt++;
    }

    for (i = 0; i < cnt; i++)
        sort(res[i].begin(), res[i].end());
    sort(res.begin(), res.end(), [](const vi &i, const vi &j) { return i[0] < j[0]; });

    printf("%d\n", res.size());

    for (auto &i : res)
    {
        for (auto j : i)
            printf("%d ", j);
        puts("-1");
    }
    return 0;
}

 

 

https://jason9319.tistory.com/98

SCC(Strongly Connected Component)