글 읽기 - 문제 오류인거 같습니다. 조건을 추가해야 할 거 같습니다

jimmy1016 1년 전 0

일단 맞은 사람의 풀이를 봤었는데, 그 풀이를 제가 만든 테스트 케이스에 넣으면 문제가 생기는거 같습니다.

사람들은 1번 노드에 대한 정보가 무조건 주어진다고 생각하고 코드를 짠 거 같은데

제가 생각한 테스트 케이스 입니다.

6 2

3 4

4 6

답 : 1

출력 : 4

다음과 같이 일이 벌어집니다. 문제에서 1번 노드에 대한 간선 정보가 무조건 주어진다는 조건이 있어야 할 거 같습니다.

#include<iostream>

int n, cnt = 0;
using namespace std;

char graph[1001][1001] = { 0 };
bool visited[1001] = { 0 };

void dfs(int num) {
    visited[num] = true;

    for (int i = 1; i <= n; i++) {
        if (graph[num][i] && !visited[i]) {
            dfs(i);
        }
    }
}


int main() {
    int m;
    cin >> n >> m;
  
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        graph[a][b] = true;
        graph[b][a] = true;
    }

    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            cnt++;
            dfs(i);
        }
    }

    cout << cnt;

    return 0;
}

jh05013 1년 전 1

해당 코드가 1번 노드에 대한 가정을 한다고 생각하신 이유가 무엇인가요?
연결 요소는 4개가 맞습니다. {1}, {2}, {3, 4, 6}, {5}로 4개입니다.

jimmy1016 1년 전 0

아 1번 노드에 대한 가정은 사실 너무 근본이 없이 막 떠오르긴 했는데요,

{1} 이렇게 단독으로만 있는것도 연결요소에 포함된다는게 이해가 안가네요, 연결된게 없는데 말이죠

djm03178 1년 전 0

연결 요소의 정의가 그렇습니다. 같은 연결 요소에 포함된 정점끼리 간선을 필요한 만큼 사용해서 서로 도달 가능하기만 하면 되는데, 간선을 0개 사용해도 되니까 자기 자신은 항상 자기 자신의 연결 요소에 속합니다.

jimmy1016 1년 전 0

그렇군요 연결 요소의 정의가 따로 있는지는 몰랐습니다. 저는 단어의미 그대로 연결된게 있을 때, 그게 총 몇가지인지 묻는 문제인걸로 파악했네요

감사합니다

djm03178 1년 전 0

단어 의미 그대로 보더라도 크기 1의 연결 요소라는 것이 이상하지는 않습니다. 자기 자신은 언제나 자기 자신과 '연결'되어 있으니까요.

댓글을 작성하려면 로그인해야 합니다.