[백준] 4196번 : 도미노 - C++

백준 4196번 : 도미노

등급 : Platinum IV

4196번: 도미노 (acmicpc.net)

4196번: 도미노

사용 알고리즘 : SCC

사용 자료구조 : Vector

 

각 도미노를 SCC 단위로 나눠주고, 각 SCC에 들어오는 간선 Indegree값을 저장해 푸는 문제.

---

  1. SCC를 구하기 위해 순방향으로 DFS, 그리고 스택에 쌓인 순서대로 역방향 DFS를 진행해준다. (기존 SCC 알고리즘)

  2. 역방향 DFS를 순회할 때 처음 방문하는 정점(Vertex)에는 SCC의 번호를 달아준다.

      이때 Visit한 점에 다시 방문할 경우, SCC번호가 같은지 확인해주고 다르다면 방문하는 SCC의 Indegree를 늘려준다.

  3. Indegree가 0인 SCC, 즉 누군가가 밀어주지 못하는 점의 갯수가 최소 쓰러뜨려야 할 도미노의 갯수가 된다.

      ( 작성 시 코드 길이를 짧게 하기 위해 DFS를 1개로 하였지만, 2개로 구현하셔도 무방합니다. )

---

#include <iostream>
#include <vector>

using namespace std;

vector <vector <int>> v;
// 그래프의 간선 정보를 기록할 배열
vector <int> rev;
// DFS의 역순으로 위상 정렬을 한 정점을 저장할 배열
int ind[100001];
// 각 SCC의 Indegree값을 저장할 배열
int snum[100001];
// 각 정점의 SCC Number를 저장할 배열
bool visit[100001];
// 방문 정보를 확인할 배열

void dfs(int x, bool opt, int num)
// DFS 함수에 Option 정보를 달아서 순방향, 역방향일 때를 구분
{
    if (!opt) snum[x] = num;
    // 역순 탐색일 때만 snum을 기입한다
    visit[x] = true;
    for (int i = 0; i < v[x].size(); i++)
    {
        int y = v[x][i];
        if (!visit[y]) dfs(y, opt, num);
        else if (!opt && snum[x] != snum[y]) ind[snum[y]]++;
        // 역순일 때, visit한 간선이 서로 다른 SCC에 속해있으면 연결된 정점의 Indegree를 늘려준다
    }
    if(opt) rev.push_back(x);
    // 순방향일 때만 정점을 위상 정렬한다
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    int n, m, x, y;
    int ans;
    cin >> t;
    while (t--)
    {
        fill_n(visit, 100001, false);
        fill_n(snum, 100001, -1);
        fill_n(ind, 100001, 0);
        ans = 0;
        int cnt = 0;
        rev.clear();
        v.clear();
        // 새로운 테스트 케이스마다 저장된 정보들을 리셋
        cin >> n >> m;
        v.resize(n + 1);
        // 정점의 번호가 1부터 저장되므로, 벡터의 크기를 n+1개로 맞춘다
        for (int i = 0; i < m; i++)
        // 그래프 정보 저장
        {
            cin >> x >> y;
            v[x].push_back(y);
        }
        for (int i = 1; i <= n; i++)
        // 순방향 DFS 탐색
        {
            if (!visit[i]) dfs(i, true, -1);
        }
        fill_n(visit, 100001, false);
        // 탐색 이후 정점 방문 정보 리셋
        for (int i = 0; i < n; i++)
        // 역방향 DFS 탐색 및 SCC의 갯수 카운트
        {
            if (!visit[rev[i]])
            {
                dfs(rev[i], false, cnt);
                cnt++;
            }
        }
        for (int i = 0; i < cnt; i++)
        // Indegree 값이 0이면 ans값을 늘려준다
        {
            if (ind[i] == 0) ans++;
        }
        cout << ans << "\n";
    }
}