eremo2002   2년 전


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

2 1

1 2  입력할 때와


2 1

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


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






jason9319   2년 전

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   2년 전

감사합니다.

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