글 읽기 - 반례좀 찾아주세여 ㅠㅠㅠ

tkatjdrkwk 5년 전 0

ㅠㅠㅠ 반례좀 찾아주세요 ㅠㅠ

#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

int N, M;
int checklist[2001];
bool visit[2001];
vector<vector<int>> V;
int total;
deque <int> DQ;


void DFS(int index)
{
	if (DQ.size() == 3)
	{
		total++; return;
	}

	for (int i = index; i <= N; i++)
	{
		if (visit[i] == false)
		{
			visit[i] = true;
			DQ.push_back(i);
			for (int j = 0; j < checklist[i]; j++)
			{
				visit[V[i][j]] = true;
			}
			DFS(i + 1);
			visit[i] = false;
			DQ.pop_back();
			for (int j = 0; j < checklist[i]; j++)
			{
				visit[V[i][j]] = false;
			}
		}
	}

}


int main()
{
	int a, b;
	scanf("%d %d", &N, &M);
	V.resize(N + 1);
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &a, &b);
		checklist[a]++;
		checklist[b]++;
		V[a].push_back(b);
		V[b].push_back(a);
	}


	DFS(1);
	printf("%d", total);
	return 0;

}

inc5025 5년 전 0

5 3

1 5

2 5

3 4

위 입력에 대해서 4가 나오는데, 정답은 3입니다.

조합하면 안되는 조합을 방문한 걸로 쳐서 넘어가려고 하신거같은데,

재귀를 위해 35~38번째 줄에서 방문으로 체크된 걸 다시 되돌리는 과정에서

문제가 생긴 것 같습니다.

choko100 5년 전 2

위에 올려주신 예시에 대한 답을 잘못 적어주신 것 같아서 정정드립니다.

5 3

1 5

2 5

3 4

의 답은 2입니다.

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

문제

문제

출처

ICPC

반례좀 찾아주세여 ㅠㅠㅠ

tkatjdrkwk 5년 전 0

inc5025 5년 전 0

choko100 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말