백준[4196] 도미노

문제 설명

문제 링크

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

4196번: 도미노

풀이

이 문제는 SCC를 이용하여 풀 수 있다.

처음에 이 문제를 보고 아무 점에서나 dfs를 돌려서 dfs를 몇 번 돌리나 카운팅 하면 될 것이라고 생각했다. 하지만 1 -> 2 -> 3 -> 4가 있을 때 1번에서 dfs가 시작하면 문제가 없지만 2, 3, 4번에서 dfs가 시작하면 1번은 처리가 되지 않는다. 

그렇기 때문에 SCC를 활용해야한다. 코사라주 알고리즘을 이용하면 stack의 최상단에는 항상 위의 예시에서 1과 같은 가장 연결이 많이 되어 있는 노드가 존재한다. 그렇기 때문에 stack에 저장된 모든 정점을 하나씩 꺼내며 dfs를 돌면 이 문제를 해결할 수 있다.

코드

#include <cstdio>
#include <vector>
#include <cstring>
#include <stack>

using namespace std;

bool visited[100005];
vector<vector<int>> v;
stack<int> s;

void dfs(int cur) {
    visited[cur] = true;
    for (auto nxt : v[cur]) {
        if (!visited[nxt]) dfs(nxt);
    }
    s.push(cur);
}

void solve() {
    int n, m; scanf("%d %d", &n, &m);
    v.clear(); v.resize(n + 1);
    while (m--) {
        int a, b; scanf("%d %d", &a, &b);
        v[a].push_back(b);
    }

    memset(visited, 0, sizeof visited);
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) dfs(i);
    }

    memset(visited, 0, sizeof visited);    
    int ans = 0;
    while (!s.empty()) {
        int cur = s.top();
        s.pop();
        if (!visited[cur]) {
            dfs(cur);
            ans++;
        }
    }
    printf("%d\n", ans);
}

int main() {
    int t; scanf("%d", &t);
    while (t--) {
        solve();
    }
}