10159 저울

BOJ::10159 저울

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

x->y 방향을 가진 map1

y->x 방향을 가진 map2

이렇게 두가지로 놓고 dfs를 사용하여 두 map에 대해 탐색한후

둘중 하나라도 visited배열에 방문 흔적이 있으면 cnt++ 해주었다.

아이디어가 쉽게 떠오르지 않아 푸는데 나름 오랫동안 생각했다.

#include <stdio.h>
using namespace std;
 
int n, m;
int map1[101][101];
int map2[101][101];
bool visited1[101];
bool visited2[101];
int res[101];
 
void dfs1(int v) {
    visited1[v]=true;
    for (int i = 1; i <= n; i++) {
        if (map1[v][i] == 1 && !visited1[i]) {
            dfs1(i);
        }
    }
}
 
void dfs2(int v) {
    visited2[v] = true;
    for (int i = 1; i <= n; i++) {
        if (map2[v][i] == 1 && !visited2[i]) {
            dfs2(i);
        }
    }
}
 
void init() {
    for (int i = 1; i <= n; i++) {
        visited1[i] = false;
    }
    for (int i = 1; i <= n; i++) {
        visited2[i] = false;
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        map1[x][y] = 1;
        map2[y][x] = 1;
    }
 
    for (int i = 1; i <= n; i++) {
        init();
        dfs1(i);
        dfs2(i);
        int cnt = 0;
        for (int j = 1; j <= n; j++) {
            if (visited1[j] || visited2[j]) {
                cnt++;
            }
        }
        res[i] = n-cnt;
    }
    for (int i = 1; i <= n; i++) {
        printf("%d\n", res[i]);
    }
}