글 읽기 - 질문입니다.

eremo2002 6년 전 0

문제에 있는 예제는 잘 나오는데

2 1

1 2 입력할 때와

2 1

1 3 입력할 때 답이 서로 다르게 나오네요.

왜 다르게 나오는지 이해가 안됩니다. 둘다 1로 나와야 하는데 아래 경우엔 출력이 2가 나와요.

​

#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

vector<int> a[1001];
bool check[1001];
void dfs(int node) {
check[node] = 1;
for (int i = 0; i < a[node].size(); i++)
{
int next = a[node][i];

if (check[next] == 0)
dfs(next);
}
}

int main()
{
ios::sync_with_stdio(false);
//freopen("input.txt", "r", stdin);
int n, m; // 정점, 간선 수
cin >> n >> m;

for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
a[u].push_back(v);

}

int c = 0;

for (int i = 1; i <= n; i++)
{
if (check[i] == 0)
{
dfs(i);
c++;
}
}

cout << c;

return 0;
}

jason9319 6년 전 1

dfs를 돌리면서 방문 안한 정점을 발견했을 때 새로운 연결요소를 발견했다고 생각하여 카운트를 증가시켜주는 방식으로 푸셨군요

for (int i = 1; i <= n; i++)
{
if (check[i] == 0)
{
dfs(i);
c++;
}
}

이 부분을 보면 for문이 1~에서 n까지 돕니다. 즉 정점 번호가 1~n까지만 존재한다고 가정하고 계산을 하는거죠

2번째 인풋의 경우 1 하고 3이면 중간에 2가 생략되었기 때문에 1에서 dfs가 돌고 2에서 dfs가 또 돌기 때문에 답이 2가 됩니다.

그런데 이러한 결과와 상관없이 어짜피 이 문제 자체는 2번째 인풋같은 입력이 주어지지 않습니다.

문제를 틀리는 원인은 이 문제는 방향이없는 무향 그래프인데 인풋을 받으면서 유향 그래프로 설계를 하셔서 틀리신거 같습니다.

int u, v;
cin >> u >> v;
a[u].push_back(v);

아래에

a[v].push_back(u);

를 추가하면 통과하실 것 같습니다.

eremo2002 6년 전 0

감사합니다.

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

문제

문제

출처

ICPC

질문입니다.

eremo2002 6년 전 0

jason9319 6년 전 1

eremo2002 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말