글 읽기 - 시간초과가 발생합니다...

cleankid99 5년 전 0

dfs로 구현하려고 했습니다.

dfs 호출을 두번하는 대신,

첫번째 dfs에서는 그 수부터 1까지의 노드를 방문하면서 true로 바꿔주고

두번째 dfs에서는 그 수부터 출발해서 노드를 방문하면서 true가 되어있는 노드를 만나자마자 바로 값을 저장하고 return 하는 식으로 구현해봤는데요

아무래도 테스트케이스가 너무 커서 시간초과가 발생하는것 같은데

힌트좀 주실 수 있을까요?

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

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

void dfs(int num) {
	if (num == 1) { // 루트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;
}

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

문제

문제

출처

ICPC

시간초과가 발생합니다...

cleankid99 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말