강한 연결 요소(Strongly Connected Component, SCC)

• 참고

  https://blog.naver.com/ndb796/221236952158

SCC는 강하게 결합된 정점 집합을 의미한다.
즉, SCC의 임의의 u와 v는 u→v , v→u 모두 가능하다는 뜻이다.

사이클이 발생하면 무조건 SCC에 해당되는 특징이 있다.

시간복잡도 : O(V+E)

![[assets/images/posts_img/Untitled 6.png

Untitled 6.png]]

class SCC {
private:
    int N, _id, _scc;
    vector<int> id, scc, cnt, dp; //scc[x] := x번 노드의 scc 번호, cnt[scc_x] := scc_x번의 scc의 집합 크기, dp[x] := src->x 의 최대 개수(bfs)
    vector<vector<int>> g, scc_g;
    stack<int> st;

    int dfs(int u) {
        id[u] = _id++;
        st.push(u);

        int parent = id[u];
        for(int v : g[u]) {
            if(id[v] == -1) parent = min(parent, dfs(v));
            else if(scc[v] == -1) parent = min(parent, id[v]);
        }

        if(parent == id[u]) {
            while(true) {
                int t = st.top(); st.pop();
                scc[t] = _scc;
                cnt[_scc]++;
                if(t == u) break;
            }
            _scc++;
        }

        return parent;
    }
    int bfs(int src, int sink) {
        dp = vector<int>(_scc, 0);
        queue<int> q;

        q.push(src); dp[src] = cnt[src];
        while(!q.empty()) {
            int here = q.front(); q.pop();
            for(int there : scc_g[here]) {
                if(dp[there] >= dp[here] + cnt[there]) continue;
                dp[there] = dp[here] + cnt[there];
                q.push(there);
            }
        }
        return dp[sink];
    }

public:
    SCC(int _N) : N(_N), _id(1), _scc(1), id(N+1, -1), scc(N+1, -1), cnt(N+1,0), g(N+1) {}

    void add_edge(int u, int v) { g[u].emplace_back(v); }
    void find_scc() {
        for(int i=1; i<=N; i++)
            if(id[i] == -1) dfs(i);
        scc_g.resize(_scc);
        for(int u=1; u<=N; u++) {
            for(int v : g[u]) {
                if(scc[u] != scc[v]) scc_g[scc[u]].emplace_back(scc[v]);
            }
        }
    }
    int solve(int S, int T) {
        return bfs(scc[S], scc[T]);
    }
};