글 읽기 - 제가 문제 이해를 잘못한걸까요?ㅠ

dhedaa 7년 전 0

이분그래프라는게 각 정점이 순환하지않으면 이분그래프가 형성된다고 이해했는데

잘못이해한건가요?

아래코드는 dfs돌리면서 정점에 방문할때마다 방문한 정점 배열 값을 1씩 증가시켜서 배열값이 2가 되면 두번 방문한다고 하고 순환이라 판단해서 짠 코드입니다.

계속 런타임에러가 뜨네요ㅠ

//1707 이분 그래프

#include <iostream>

using namespace std;

int tc, v, e, x, y, cnt;
int map[20002][20002];
bool isAll = true;

void dfs(int a, int *visited)
{	
	for (int i = 1; i <= v; i++)
	{
		if (visited[i] > 1)
		{
			isAll = false;
			return;
		}
	}
	for (int i = 1; i <= v; i++)
	{
		if (map[a][i] == 1 && map[i][a] == 1)
		{
			map[a][i] = map[i][a] = 0;
			visited[i]++;			
			dfs(i, visited);
						
		}
	}	
}

int main()
{
	cin >> tc;
	for (int i = 0; i < tc; i++)
	{
		cin >> v >> e;
		int *visited = new int[v + 1];
		for (int j = 0; j < v + 1; j++)
			visited[j] = 0;
        
		for (int j = 0; j < e; j++)
		{
			cin >> x >> y;
			map[y][x] = map[x][y] = 1;
		}	
		visited[1]++;
		dfs(1, visited);
        
		if (isAll == true)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
		delete[] visited;
	}

}

kdk8361 7년 전 1

이분 그래프는 짝수개의 정점으로 이루어진 순환은 존재할 수 있습니다.

o o

| X |

o o

이런식으로요.

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

문제

문제

출처

ICPC

제가 문제 이해를 잘못한걸까요?ㅠ

dhedaa 7년 전 0

kdk8361 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말