[백준] 4196번 도미노

4196 도미노

문제

---

도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러뜨릴 수 있다. 그러나, 가끔씩 도미노가 다른 블록을 넘어뜨리지 못하게 배치되어 있다면, 우리는 다음 블록을 수동으로 넘어뜨려야 한다.

이제 각 도미노 블록의 배치가 주어졌을 때, 모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최솟값을 구하자.

입력

---

첫 번째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 N, M이 주어지며 두 수는 100,000을 넘지 않는다. N은 도미노의 개수를, M은 관계의 개수를 나타낸다. 

도미노 블록의 번호는 1과 N 사이의 정수다. 다음 M개의 줄에는 각각 두 정수 x, 가 주어지는데, 이는 x번 블록이 넘어지면 y번 블록도 넘어짐을 뜻한다.

출력

---

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 정답은 손으로 넘어뜨려야 하는 최소의 도미노 블록 개수이다.

---

풀이)

SCC와 약간의 위상정렬 방법(indegree[]배열)를 이용해서 푸는 문제이다.

과정

1. 블록끼리의 연결을 가지고, kosaraju algorithm을 이용해 SCC를 구한다.

   kosaraju algorithm : 2번의 dfs를 이용, stack을 활용

2. SCC끼리의 연결 상태를 저장한다.

   ex) SCC 1 -> SCC 2 로 연결이 가능하다면 SCC 2의 indegree(들어오는 간선 수)를 +1 시켜준다.

3. SCC 중 indegree 값이 0인 SCC의 개수를 세어서 출력한다. 

(그림으로 예를 들자면)

이런식으로 블록이 연결되어있다면

아래처럼 SCC는 2개가 나오고, SCC 1과 SCC 2는 1->2로 연결될 수 있다.

1->2 로 간선이 연결될 수 있으니깐 SCC 2의 간선 개수 +1

그럼 총 SCC 개수는 2개이고 indegree가 0인 SCC는 1개니깐

결론적으로 손으로 넘어트려야 하는 블록의 최소 개수는 1개이다.

(indegree가 1이상인 SCC에 속한 블록들은 다른 SCC 블록들에 의해 넘어질 수 있다고 생각하면 된다.) 

코드)

#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
using namespace std;
#define MAX 100002
int n, m;
vector <int> adj[MAX]; //kosaraju dfs1
vector <int> trans_adj[MAX]; //kosaraju dfs2
vector <int> connect_scc[MAX]; //SCC 끼리의 연결상태 저장
int indegree[MAX]; //SCC마다 들어오는 간선의 수 저장
bool visited[MAX];
stack<int> st;
int SCC[MAX]; //각 블록이 어떤 SCC에 속하는지 저장
 
void dfs(int node) {
    visited[node] = true;
    for (int i = 0; i < adj[node].size(); i++) {
        int next = adj[node][i];
        if (visited[next]) continue;
        dfs(next);
    }
    st.push(node);
}
void dfs2(int node,int idx) {
    SCC[node] = idx; //해당 블록의 SCC번호를 저장
 
    for (int i = 0; i < trans_adj[node].size(); i++) {
        int next = trans_adj[node][i];
        if (SCC[next] == 0) {//연결된 블록이 아직 어떤 SCC에도 해당이 되지 않은 블록이라면 같은 SCC 번호로 속하게해줌
            dfs2(next, idx);
        }
        else if(SCC[next] != SCC[node]) { //연결된 블록이 다른 SCC에 속한 블록이라면
            indegree[SCC[node]]++; 
            connect_scc[SCC[next]].push_back(SCC[node]); //SCC끼리의 연결 상태 저장 
            //*주의점*  trans_adj는 블록의 연결상태를 반대로 저장한 것이므로
            //            SCC끼리의 연결상태를 저장할 때 현재SCC -> 다른 SCC로 연결상태를 저장하면 안되고
            //            원래 연결상태를 생각해서 다른 SCC -> 현재 SCC 로 연결상태를 저장해줘야한다.
        }
        
    }
}
int main() {
    int test_case;
    scanf("%d", &test_case);
    while (test_case--)
    {
        scanf("%d %d", &n, &m);
        int x, y;
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            adj[x].push_back(y);
            trans_adj[y].push_back(x);
        }
 
        //kosaraju dfs1
        for (int i = 1; i <= n; i++) {
            if (visited[i]) continue;
            dfs(i);
        }
        //kosaraju dfs2
        int idx = 1; //SCC 번호
        while (st.size())
        {
            int here = st.top();
            st.pop();
            if (SCC[here] != 0) { //이미 SCC에 속한 블록이라면 pass
                continue;
            }
            else {//속하지 않은 블록이라면
                SCC[here] = idx; //해당 블록에 SCC 번호 저장해주고
                dfs2(here, idx); //dfs 2수행
                idx++; //다음 SCC번호를 위해 +1
            }
            
        }
        
        //SCC끼리의
        int result = 0;
        for (int i = 1; i < idx; i++) {
            if (indegree[i] == 0) result++;
        }
        printf("%d\n", result);
 
        //다음 test_case를 위한 초기화
        for (int i = 1; i <= n; i++) {
            adj[i].clear();
            trans_adj[i].clear();
            indegree[i] = 0;
            visited[i] = false;
            connect_scc[i].clear();
            SCC[i] = 0;
        }
        
    }
    
 
    return 0;
}