강한 결합 요소(SCC) 알고리즘 solution들 정리 220823

백준 BOJ 2150번 : Strongly Connected Component

문제 난이도 : Platinum V

알고리즘 분류 : 강한 결합 요소 (SCC)

 

방향 그래프가 주어질 때, 이들을 SCC로 나누어 출력하는 문제이다.

여기서 말하는 SCC(Strongly Connected Component)란, 한 Component 내의 어떤 두 점 사이에도 이동이 가능한 요소를 말한다. (SCC를 나눌 때는 당연히 한 Component의 크기가 최대가 되도록 나누어야 한다.)

 

그래프를 입력받고 adj 벡터에 간선들을 저장해주는 부분은 기본적이므로 설명을 생략한다.

이제 DFS 방식으로 노드들을 탐색하며, 노드 번호를 방문하는 순서대로 오름차순으로 매긴다. (nnum 벡터에 저장)

즉, 번호를 먼저 매기는 것이긴 하지만 아무튼 번호가 작은 것부터 번호가 큰 순서대로 노드들을 방문하게 된다.

 

재귀적으로 노드들을 탐색하는데, 1. 아직 방문하지 않은 노드, 2. 방문은 했으나 아직 scc로 선택되지 않은 (!ch[y]) 노드들 중 번호가 가장 작은 것이 자기 자신일 경우, 이 노드들은 순환을 통해 현재 노드로는 되돌아올 수 있으나 자기 자신보다 더 작은 번호의 노드로는 더 이상 거슬러 올라가지 못한다는 뜻이므로 SCC임을 알 수 있다.

 

그러면 이 노드들을 모두 선택(ch[y] = true) 해주고 임시 벡터에 저장하여 2차원 벡터인 scc 벡터에 push_back 해준다.

이제 scc 벡터를 정렬하여 답을 출력해주면 된다.

 

(여담으로 아래 코드에서 cnum(component number), ccnt(component count) 값은 이 문제에서는 필요 없으나, 다른 SCC 문제를 풀 때 유용하다.)

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    adj.resize(N+1);

    while(M--) {
        int a, b; cin >> a >> b;

        adj[a].push_back(b);
    }

    nnum.resize(N+1);
    cnum.resize(N+1);
    ch.resize(N+1);

    for(int i=1; i<=N; i++)
        if(nnum[i] == 0) dfs(i);

    sort(scc.begin(), scc.end());

    cout << scc.size() << "\n";

    for(int i=0; i<scc.size(); i++) {
        for(int j=0; j<scc[i].size(); j++) cout << scc[i][j] << " ";
        cout << -1 << "\n";
    }
}

 

 

백준 BOJ 4196번 : 도미노

문제 난이도 : Platinum IV

알고리즘 분류 : 강한 결합 요소 (SCC)

 

N개의 도미노가 M개의 연결 관계에 의해 연결되어 있을 때, 모든 도미노를 넘어뜨리기 위해 쓰러뜨려야 하는 최소 도미노의 개수를 구하는 문제이다.

 

같은 scc인 도미노는 어떤 것을 넘어뜨려도 scc 내의 도미노들은 모두 넘어지게 된다.

따라서, scc 내의 관계는 신경 쓸 필요 없고 scc와 scc 사이의 연결 관계에 대해 생각해보자.

다른 scc에서 현재 scc로 들어오는 간선이 있는 경우 다른 scc를 먼저 선택하면 현재 scc로의 이동이 가능하므로 모두 넘어뜨릴 수 있다.

따라서 scc들 중에서 들어오는 간선이 없는 scc의 개수를 세어주면 된다.

 

이를 구현하기 위해서는, 모든 간선들을 다시 체크해보면서 간선이 서로 다른 두 scc에 속한 노드 사이를 연결할 때, 해당 간선이 가리키는 scc 번호의 ind 값을 1 추가해주고 최종 ind 값이 0인 scc들의 개수를 세어주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    while(T--) {
        int N, M; cin >> N >> M;

        adj.clear();
        adj.resize(N+1);

        while(M--) {
            int a, b; cin >> a >> b;

            adj[a].push_back(b);
        }

        nnum.clear();   nnum.resize(N+1);
        cnum.clear();   cnum.resize(N+1);
        ch.clear();     ch.resize(N+1);

        scc.clear();
        ncnt = ccnt = 0;

        for(int i=1; i<=N; i++)
            if(nnum[i] == 0) dfs(i);

        sort(scc.begin(), scc.end());

        vector<int> ind(N+1);

        for(int i=1; i<=N; i++)
            for(int j=0; j<adj[i].size(); j++) {
                int x = adj[i][j];

                if(cnum[i] != cnum[x]) ind[cnum[x]]++;
            }

        int ans = 0;
        for(int i=1; i<=ccnt; i++)
            if(ind[i] == 0) ans++;

        cout << ans << "\n";
    }
}

 

 

 

백준 BOJ 24131번 : 宣伝 (Advertisement)

문제 난이도 : Platinum V

알고리즘 분류 : 강한 결합 요소 (SCC)

 

N명의 사람이 있고, M개의 쌍에 대해 a번 사람이 b번 사람의 연락처를 알고 있다고 할 때, 정보를 처음 전달했을 때 연락처들을 통해 모든 사람에게 정보가 전달될 수 있게 하기 위해 처음에 정보를 전달해야 하는 최소 사람 수를 구하는 문제이다.

 

위의 도미노 문제와 같은 논리가 적용될 수 있음을 알 수 있다.

따라서 테스트케이스 부분의 구현만 제외하면 나머지는 동일한 풀이로 풀 수 있다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    adj.resize(N+1);

    while(M--) {
        int a, b; cin >> a >> b;

        adj[a].push_back(b);
    }

    nnum.resize(N+1);
    cnum.resize(N+1);
    ch.resize(N+1);

    for(int i=1; i<=N; i++)
        if(nnum[i] == 0) dfs(i);

    sort(scc.begin(), scc.end());

    vector<int> ind(N+1);

    for(int i=1; i<=N; i++)
        for(int j=0; j<adj[i].size(); j++) {
            int x = adj[i][j];

            if(cnum[i] != cnum[x]) ind[cnum[x]]++;
        }

    int ans = 0;
    for(int i=1; i<=ccnt; i++)
        if(ind[i] == 0) ans++;

    cout << ans << "\n";
}

 

 

백준 BOJ 13232번 : Domain clusters

문제 난이도 : Gold I

알고리즘 분류 : 강한 결합 요소 (SCC)

 

N개의 도메인들의 연결 관계가 주어질 때, 서로 이동이 가능한 가장 큰 도메인 집합의 크기를 구하는 문제이다.

 

가장 큰 scc의 크기를 구하라는 것과 동치이므로, scc들을 구해주고 그들 중 가장 scc[i].size()가 큰 것을 답으로 구해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    adj.resize(N+1);

    while(M--) {
        int a, b; cin >> a >> b;

        adj[a].push_back(b);
    }

    nnum.resize(N+1);
    cnum.resize(N+1);
    ch.resize(N+1);

    for(int i=1; i<=N; i++)
        if(nnum[i] == 0) dfs(i);

    sort(scc.begin(), scc.end());

    int ans = 0;

    for(int i=0; i<scc.size(); i++)
        ans = max(ans, (int)scc[i].size());

    cout << ans << "\n";
}

 

 

백준 BOJ 1506번 : 경찰서

문제 난이도 : Platinum V

알고리즘 분류 : 강한 결합 요소 (SCC)

 

각 도시에 경찰서를 세우는 비용이 주어지고, 도시 사이의 단방향 도로들이 주어질 때, 서로 연결된 도시(순환이 가능해야함)들 사이에서는 한 개 이상의 경찰서가 있어야한다고 할 때 이러한 조건을 만족하기 위한 최소 경찰서 설치 비용을 구하는 문제이다.

 

같은 SCC 내에서는 하나의 경찰서만 있으면 된다.

따라서 SCC 알고리즘을 돌려준 이후 각 SCC들에 대해 비용이 가장 작은 노드의 비용을 합해서 답으로 구해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<int> v(N+1);
    for(int i=1; i<=N; i++) cin >> v[i];

    adj.resize(N+1);

    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++) {
            char c; cin >> c;

            if(c == '1') adj[i].push_back(j);
        }

    nnum.resize(N+1);
    cnum.resize(N+1);
    ch.resize(N+1);

    for(int i=1; i<=N; i++)
        if(nnum[i] == 0) dfs(i);

    sort(scc.begin(), scc.end());

    int ans = 0;

    for(int i=0; i<scc.size(); i++) {
        int Min = INT_MAX;

        for(int j=0; j<scc[i].size(); j++)
            Min = min(Min, v[scc[i][j]]);

        ans += Min;
    }

    cout << ans << "\n";
}

 

 

 

백준 BOJ 3977번 : 축구 전술

문제 난이도 : Platinum IV

알고리즘 분류 : 강한 결합 요소 (SCC)

 

N개의 노드와 M개의 단방향 간선이 주어질 때, 하나의 노드를 선택하여 모든 노드에 도달할 수 있게 할 때, 가능한 노드의 번호가 있으면 오름차순으로 모두 출력하고, 그렇지 않은 경우 Confused를 출력하는 문제이다.

 

위의 도미노 문제 아이디어의 연장으로 풀이할 수 있다.

indegree가 0인 scc는 다른 scc에서 올 수 없으므로 시작점으로 반드시 선택해주어야 한다.

따라서 만약 indegree가 0인 scc가 2개 이상이면 한 노드에서 모든 노드에 도달하는 것이 불가능하다.

그러므로 이 경우에는 Confused를 출력해준다.

 

만약 indegree가 0인 scc가 1개인 경우 해당 scc의 어떤 원소에서 시작하여도 모든 노드에 도달할 수 있다.

따라서 해당 노드들을 오름차순으로 모두 출력해주면 된다.

 

여담으로 indegree가 0인 scc가 없는 경우는 존재하지 않는다.

귀류법으로 만약 그러한 indegree가 존재한다고 가정할 경우, 이는 사이클이므로 scc 알고리즘에 의해 이미 더 큰 scc에  소속되어있어야 한다.

따라서 indegree가 0인 scc가 1개이거나 그보다 많은 경우로만 나누어 생각해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    while(T--) {
        int N, M; cin >> N >> M;

        adj.clear();
        adj.resize(N+1);

        while(M--) {
            int a, b; cin >> a >> b;

            adj[a+1].push_back(b+1);
        }

        nnum.clear();   nnum.resize(N+1);
        cnum.clear();   cnum.resize(N+1);
        ch.clear();     ch.resize(N+1);

        scc.clear();
        ncnt = ccnt = 0;

        for(int i=1; i<=N; i++)
            if(nnum[i] == 0) dfs(i);

        sort(scc.begin(), scc.end());

        vector<int> ind(N+1);

        for(int i=1; i<=N; i++)
            for(int j=0; j<adj[i].size(); j++) {
                int x = adj[i][j];

                if(cnum[i] != cnum[x]) ind[cnum[x]]++;
            }

        int cnt = 0, idx;
        for(int i=1; i<=ccnt; i++)
            if(ind[i] == 0) {
                cnt++;
                idx = i;
            }

        if(cnt == 1) {
            for(int i=1; i<=N; i++)
                if(cnum[i] == idx) cout << i-1 << "\n";
        }
        else cout << "Confused\n";

        cout << "\n";
    }
}

 

 

백준 BOJ 6543번 : 그래프의 싱크

문제 난이도 : Platinum IV

알고리즘 분류 : 강한 결합 요소 (SCC)

 

그래프의 모든 노드에서 어떤 노드로 도달하는 경로가 존재한다면, 이 노드를 그래프의 싱크라고 정의할 때, 주어진 그래프의 싱크 노드들을 모두 출력하는 문제이다.

 

간선이 단방향 간선이므로, outdegree(외부로 나가는 간선의 수)가 0인 scc의 모든 원소들을 구해주면 된다.

outdegree 값은 위의 도미노 문제에서 풀이한 것과 비슷한 방식으로, 모든 간선에 대해 검사할 때 서로 다른 scc 사이의 간선인 경우 해당 간선의 출발 노드에 outdegree를 1 더해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    while(true) {
        int N; cin >> N;
        if(N == 0) break;

        int M; cin >> M;

        adj.clear();
        adj.resize(N+1);

        while(M--) {
            int a, b; cin >> a >> b;

            adj[a].push_back(b);
        }

        nnum.clear();   nnum.resize(N+1);
        cnum.clear();   cnum.resize(N+1);
        ch.clear();     ch.resize(N+1);

        scc.clear();
        ncnt = ccnt = 0;

        for(int i=1; i<=N; i++)
            if(nnum[i] == 0) dfs(i);

        sort(scc.begin(), scc.end());

        vector<int> oud(N+1);

        for(int i=1; i<=N; i++)
            for(int j=0; j<adj[i].size(); j++) {
                int x = adj[i][j];

                if(cnum[i] != cnum[x]) oud[cnum[i]]++;
            }

        for(int i=1; i<=N; i++)
            if(oud[cnum[i]] == 0) cout << i << " ";

        cout << "\n";
    }
}

 

 

백준 BOJ 4305번 : 성격 진단 테스트

문제 난이도 : Platinum IV

알고리즘 분류 : 강한 결합 요소 (SCC)

 

N개의 5지선다 문제가 주어지고, 5개 중 가장 선호하는 항목을 고른다고 할 때, N개의 선호 관계를 활용하여 각 그룹의 원소들을 출력하여 같은 그룹의 어떤 두 원소를 뽑아도 모순 관계가 발생하게 그룹화시키는 문제이다.

(예를 들어 a, b 중에서 a를 뽑고, b, c 중에서 b를 뽑고, c, a 중에서 c를 뽑는다면 a > b > c > a로 모순이 발생하고, 출력으로 a b c를 출력해주면 된다.)

 

잘 생각해보면 SCC를 이루는 원소들끼리는 오갈 수 있는 사이클이 존재하므로, 단순히 SCC 그룹별로 원소들을 출력해주면 된다.

대문자 알파벳 하나씩만 입력으로 주어진다고 하였으므로, N은 최대 26이다.

나의 경우에는 무시하고 N = 26이라고 가정하고 scc를 돌린 다음에, scc[i][0] 값이 입력에 없었던 값이면 해당 줄은 skip하는 방식으로 구현하였다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    while(true) {
        int N = 26;

        int M; cin >> M;
        if(M == 0) break;

        adj.clear();
        adj.resize(N+1);

        vector<bool> u(N+1);

        while(M--) {
            vector<char> v(6);
            for(int i=0; i<6; i++) {
                cin >> v[i];

                u[v[i]-'A'+1] = true;
            }

            for(int i=0; i<6; i++) {
                if(v[i] == v[5]) continue;

                adj[v[i]-'A'+1].push_back(v[5]-'A'+1);
            }
        }

        nnum.clear();   nnum.resize(N+1);
        cnum.clear();   cnum.resize(N+1);
        ch.clear();     ch.resize(N+1);

        scc.clear();
        ncnt = ccnt = 0;

        for(int i=1; i<=N; i++)
            if(nnum[i] == 0) dfs(i);

        sort(scc.begin(), scc.end());

        for(int i=0; i<scc.size(); i++) {
            if(!u[scc[i][0]]) continue;

            for(int j=0; j<scc[i].size(); j++) cout << char('A' + scc[i][j] - 1) << " ";
            cout << "\n";
        }

        cout << "\n";
    }
}

 

 

백준 BOJ 25488번 : 토큰

문제 난이도 : Platinum IV

알고리즘 분류 : 강한 결합 요소 (SCC)

 

단방향 간선을 가진 그래프가 주어질 때, N개의 점의 목록 A와 B가 주어질 때, 처음에 A의 위치에 있던 N개의 토큰들을 그래프 간선만 따라서 이동시켜서 B의 위치들로 옮긴 뒤, 다시 A로 돌아올 수 있는지를 구하는 문제이다.

 

SCC를 돌린 후, A의 점들과 B의 점들이 각 SCC 그룹에 속하는 개수가 일치하면 Yes이고, 그 외에는 No이다.

여담으로 어제 대회 때 이 문제를 풀기 위해서 대회 시간에 SCC를 처음 공부해서 풀었다. (짤 줄은 몰랐지만 개념은 알고 있었기에 SCC로 풀리는 것이 너무 자명해보여서..)

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj, scc;
int ncnt = 0, ccnt = 0;
stack<int> s;
vector<int> nnum, cnum;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    adj.resize(N+1);

    while(M--) {
        int a, b; cin >> a >> b;

        adj[a].push_back(b);
    }

    nnum.resize(N+1);
    cnum.resize(N+1);
    ch.resize(N+1);

    for(int i=1; i<=N; i++)
        if(nnum[i] == 0) dfs(i);

    sort(scc.begin(), scc.end());

    int K; cin >> K;

    vector<int> v(ccnt+1), u(ccnt+1);

    for(int i=0; i<K; i++) {
        int x; cin >> x;

        v[cnum[x]]++;
    }

    for(int i=0; i<K; i++) {
        int x; cin >> x;

        u[cnum[x]]++;
    }

    if(v == u) cout << "YES\n";
    else cout << "NO\n";
}

 

 

백준 BOJ 7042번 : Cow Ski Area

문제 난이도 : Platinum IV

알고리즘 분류 : 강한 결합 요소 (SCC)

 

R x C 크기의 스키장의 높낮이가 주어질 때, 상하좌우로 이동하되 높은 곳에서 낮은 곳 또는 높이가 같은 곳으로만 이동이 가능하며, 특정 두 칸을 연결하는 리프트를 몇 개 설치하여 모든 칸 사이의 이동이 가능하도록 할 때 설치해야하는 최소 리프트의 수를 구하는 문제이다.

 

SCC를 돌려준 뒤 indegree가 0인 component의 수와 outdegree가 0인 component의 수 중 큰 것이 답이 된다.

여기까지는 그래프 몇 개를 그려보고 빨리 파악을 했는데, 간단한 예외를 못 찾아서 30분은 헤맸다.

만약 component가 단 1개뿐이라면, 위의 풀이대로라면 답이 1이 나와야 하는데 이 경우는 답이 0이 되어야 한다.

이와 같은 반례 처리에 주의하자.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int C, R; cin >> C >> R;

    vector<vector<int>> v(R+1, vector<int>(C+1));

    for(int i=1; i<=R; i++)
        for(int j=1; j<=C; j++) cin >> v[i][j];

    int N = R * C;

    adj.resize(N+1);

    int di[4] = {1, -1, 0, 0};
    int dj[4] = {0, 0, 1, -1};

    for(int i=1; i<=R; i++)
        for(int j=1; j<=C; j++)
            for(int k=0; k<4; k++) {
                int ni = i + di[k];
                int nj = j + dj[k];

                if(ni <= 0 || nj <= 0 || ni > R || nj > C) continue;

                if(v[i][j] >= v[ni][nj]) adj[(i-1)*C + j].push_back((ni-1)*C + nj);
            }

    nnum.resize(N+1);
    cnum.resize(N+1);
    ch.resize(N+1);

    for(int i=1; i<=N; i++)
        if(nnum[i] == 0) dfs(i);

    sort(scc.begin(), scc.end());

    if(ccnt == 1) {
        cout << 0 << "\n";
        return 0;
    }

    vector<int> ind(N+1), oud(N+1);

    for(int i=1; i<=N; i++)
        for(int j=0; j<adj[i].size(); j++) {
            int x = adj[i][j];

            if(cnum[i] != cnum[x]) {
                ind[cnum[x]]++;
                oud[cnum[i]]++;
            }
        }

    int incnt = 0, oucnt = 0;
    for(int i=1; i<=ccnt; i++) {
        if(ind[i] == 0) incnt++;
        if(oud[i] == 0) oucnt++;
    }

    int ans = max(incnt, oucnt);

    cout << ans << "\n";
}