글 읽기 - 반례를 주시면 감사하겠습니다.

ksc1008 2년 전 0

20%부근에서 실패로 뜨네요.

어디가 문제인지 도저히 모르겠습니다.

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

struct Node {
	vector<int>Edges;
};


Node nodes[2001];
bool dfsVisited[2001];
bool bfsVisited[2001];

queue<int>bfs;

int N, M;

void Link(int node1, int node2) {
	nodes[node1].Edges.push_back(node2);
	nodes[node2].Edges.push_back(node1);
}

void SortAll() {
	for (int i = 0; i < N; i++) {
		if(!nodes[i].Edges.empty())
			sort(nodes[i].Edges.begin(), nodes[i].Edges.end());
	}
}

void DFS(int index) {
	printf("%d ", index);
	dfsVisited[index] = true;
	for (int i = 0; i < nodes[index].Edges.size(); i++) {
		if (!dfsVisited[nodes[index].Edges[i]]) {
			DFS(nodes[index].Edges[i]);
		}
	}
}

void BFS(int index) {
	bfs.pop();
	printf("%d ", index);
	bfsVisited[index] = true;
	for (int i = 0; i < nodes[index].Edges.size(); i++) {
		if (!bfsVisited[nodes[index].Edges[i]]) {
			bfs.push(nodes[index].Edges[i]);
			bfsVisited[nodes[index].Edges[i]] = true;
		}
	}
}

int main() {
	cin >> N >> M;
	int startNode;
	cin >> startNode;
	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		Link(a, b);
	}
	SortAll();

	DFS(startNode);
	cout << endl;

	bfs.push(startNode);
	while (!bfs.empty()) {
		BFS(bfs.front());
	}
}

ksoosung77 2년 전 1

반례:

5 3 1
1 5
3 5
5 2

답:

1 5 2 3

ksc1008 2년 전 0

인덱스가 1부터 시작하는걸 놓치고 있었네요

정말 감사합니다!

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

문제

문제

출처

ICPC

반례를 주시면 감사하겠습니다.

ksc1008 2년 전 0

ksoosung77 2년 전 1

ksc1008 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말