글 읽기 - 1260번 질문에 나온 반례는 다 맞는데 틀렸습니다..

ehdrhs329 4년 전 0

https://www.acmicpc.net/board/view/24356

여기에 나온 반례들과 질문 게시판에 나온 반례들을 다 해봤는데 틀리네요.. 조언 부탁드립니다.

#include <iostream>
void DFS(int edge[][2], int n, int m, int start);
void BFS(int edge[][2], int n, int m, int start);
int pri_find(int n, int pri[], int num);
int main(void) {
	int n, m, start, edge[10001][2];
	std::cin >> n >> m >> start;
	for (int i = 1; i <= m; i++) {
		std::cin >> edge[i][0] >> edge[i][1];
	}
	DFS(edge, n, m, start);
	std::cout << "\n";
	BFS(edge, n, m, start);
	std::cout << "\n";
	return 0;
}
int pri_find(int n, int pri[], int num) {
	for (int i = 1; i <= n; i++) {
		if (pri[i] == num)
			return 1;
	}
	return 0;
}
void DFS(int edge[][2], int n, int m, int start) {
	int min = 1001, pri[1001], num;
	pri[1] = start;
	std::cout << pri[1];
	for (int i = 2; i <= n; i++) {
		min = 1001;
		for (int j = 1; j <= m; j++) {
			if (edge[j][0] == start && edge[j][1] < min && pri_find(n, pri, edge[j][1]) == 0) {
				min = edge[j][1];
			}
			else if (edge[j][1] == start && edge[j][0] < min && pri_find(n, pri, edge[j][0]) == 0) {
				min = edge[j][0];
			}
		}
		start = min;
		pri[i] = min;
		if (min == 1001) {
			if (i <= n && pri[num] != 0) {
				start = pri[num];
				num--;
				i--;
			}
			else {
				pri[i] = 0;
			}
		}
		else {
			num = i;
		}
	}
	for (int i = 2; i <= n; i++) {
		if(pri[i] != 0)
			std::cout << " " << pri[i];
	}
}
void BFS(int edge[][2], int n, int m, int start) {
	int min = 1001, pri[1001], num = 2;
	for (int i = 1; i <= n; i++) {
		pri[i] = 0;
	}
	pri[1] = start;
	std::cout << pri[1];
	for (int i = 2; i <= n; i++) {
		min = 1001;
		for (int j = 1; j <= m; j++) {
			if (edge[j][0] == start && edge[j][1] < min && pri_find(n, pri, edge[j][1]) == 0) {
				min = edge[j][1];
			}
			else if (edge[j][1] == start && edge[j][0] < min && pri_find(n, pri, edge[j][0]) == 0) {
				min = edge[j][0];
			}
		}
		pri[i] = min;
		if (min == 1001) {
			if (i <= n && pri[num] != 0) {
				start = pri[num];
				num++;
				i--;
			}
			else {
				pri[i] = 0;
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		if (pri[i] != 0)
			std::cout << " " << pri[i];
	}
}

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

문제

문제

출처

ICPC

1260번 질문에 나온 반례는 다 맞는데 틀렸습니다..

ehdrhs329 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말