글 읽기 - 바로 틀렸습니다가 나옵니다.. 테스트케이스가 필요할것같습니다.

cleankid99 5년 전 0

dfs로 구현하였습니다.

예제 케이스도 잘 나오고

혹시나해서 질문에 있는 예시들도 넣어봤는데

어떤게 문제가 되는지 궁금합니다.

바로 틀렸습니다가 나옵니다,,

#include <cstdio>
#include <vector>
using namespace std;

vector<vector<int> > adj;
vector<bool> chk;
int cp;

void dfs(int num) {
	if (num == 1 || chk[num]==true) { // 루트1까지 도달 or 이미 방문한적이 있음
		cp = num;
		return;
	}

	chk[num] = true; // 방문시 true
	
	for (int i = 0; i < adj[num].size(); i++) {
		int next = adj[num][i];
		if (next < num && chk[next]==false) { // 값이 작아야 부모노드
			dfs(next);
		}
		else if (next < num && chk[next] == true) {//이미 방문한적이 있음(다른 노드에서 시작해서 온적이 있음)
			cp = next;
			return;
		}
	}

}

int main() {
	int n, m;
	scanf("%d", &n);
	adj.resize(n + 1);
	chk.resize(n + 1);
	for (int i = 0; i < n-1; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		adj[x].push_back(y);
		adj[y].push_back(x);		
	}

	scanf("%d", &m);

	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d %d", &x ,&y);
		dfs(x);
		dfs(y);

		printf("%d\n", cp);

		chk.clear();
		chk.resize(n + 1, false);
	}



	return 0;
}

luniro 5년 전 1

19번째 줄에서 값이 작아야 부모노드라는 조건이 어디서 나온건가요?

cleankid99 5년 전 0

아 그 조건이 성립하지가 않는군요... 감사합니다..

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

문제

문제

출처

ICPC

바로 틀렸습니다가 나옵니다.. 테스트케이스가 필요할것같습니다.

cleankid99 5년 전 0

luniro 5년 전 1

cleankid99 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말