글 읽기 - 50퍼센트에서 틀렸다고 뜹니다ㅜ

dhedaa 7년 전 0

50퍼센트에서 틀렸다고 뜨네요.

뭐가 문제일까요?

//11724 연결요소

#include <iostream>

using namespace std;

int n, m, x, y, cnt;
int map[1001][1001];

void dfs(int a)
{
	for (int i = 1; i <= n; i++)
	{
		if (map[a][i] == 1 && map[i][a] == 1)
		{
			map[i][a] = map[a][i] = 0;
			dfs(i);
		}
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		map[x][y] = map[y][x] = 1;
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (map[i][j] == 1)
			{
				dfs(i);
				cnt++;
			}
		}
	}
	cout << cnt << endl;
}

qja0950 7년 전 0

간선이 하나도 없는 경우는 판단하지 못하네요!

dhedaa 7년 전 0

간선이하나도 없는 경우는 간선 M의 범위가 1이상이어서 고려하지 않았어요 ㅠㅠ

그 경우도 한번 예외처리 해봤는데 안되네여 ㅠ

qja0950 7년 전 9

우엥.. 요렇게 힌트를 드리면 해결하실 줄 알았는데.. ㅜㅜ

더 자세히 설명해드릴게욥

예를들어,

N = 5이고 M = 1라서

간선이 2 3만 연결된 상황이라고 생각하면

연결 요소의 개수는 4개인데, 위 코드에서는 1개로 나옵니다!

즉, 위 코드에서는 혼자있는 정점을 세주지 못해요!

dhedaa 7년 전 1

헐 그경우가 있었구나...ㅠㅠ

감사합니다ㅠㅠ

정답됐어요 ㅠ

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