글 읽기 - DFS와 BFS 질문입니다

raekim 5년 전 0

문제 예제는 제대로 동작하고 질문게시판에 있는 웬만한 반례들 돌려도 잘 돌아가는데

제출하면 틀리네요 ㅜㅜ 어디가 틀린건가요..

#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
using namespace std;

int N, M, V;	// N:number of vertices, M:number of edges, V:starting vertex
bool connected[1001][1001];	// connected[x][y] : are vertices x and y connected?
bool visited[1001];	// visited[x] : has vertex x been visited before?

void input() {
	scanf("%d %d %d", &N, &M, &V);
	for (int i = 0; i < M; ++i) {
		int x, y;
		scanf("%d %d", &x, &y);
		connected[x][y] = true;
		connected[y][x] = true;
	}
}

void initialize() {
	memset(visited, false, sizeof(visited));
}

void DFS() {
	initialize();

	/* Visit the starting vertex */
	visited[V] = true;
	printf("%d", V);
	stack<int> st;
	st.push(V);

	/* Visit the rest */
	while(!st.empty()) {
		for (int i = 1; i <= N; ++i) {
			if (!visited[i] && connected[st.top()][i]) {
				visited[i] = true;
				printf(" %d", i);
				st.push(i);
				i = 1;
			}
		}
		st.pop();
	}

	printf("\n");
}

void BFS() {
	initialize();

	/* Visit the starting vertex */
	visited[V] = true;
	printf("%d", V);
	queue<int> q;
	q.push(V);

	/* Visit the rest */
	while (!q.empty()) {
		for (int i = 1; i <= N; ++i) {
			if (!visited[i] && connected[q.front()][i]) {
				visited[i] = true;
				printf(" %d", i);
				q.push(i);
			}
		}
		q.pop();
	}

	printf("\n");
}

int main() {
	input();
	DFS();
	BFS();
}

rubix 5년 전 1

반례입니다.

3 2 2

1 3

2 3

jh05013 5년 전 1

게시판이 6페이지나 되는데 나올 만한 반례는 다 나오지 않았을까 싶습니다.

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

raekim 5년 전 0

해결되었습니다 ㅜㅜ!

다음부턴 질문 올리기 전에 게시판을 더 꼼꼼하게 봐야겠어요 답변감사합니다

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

문제

문제

출처

ICPC

DFS와 BFS 질문입니다

raekim 5년 전 0

rubix 5년 전 1

jh05013 5년 전 1

raekim 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말