글 읽기 - 11897번 시간초과인데 고수님들 부탁드립니다 ㅜㅜ

khx5558 5년 전 0

DFS도중 삭제 하는 부분을 제외하고 탐색하는 방법을 이용했는데 시간초과가 뜨네요 ㅠㅠ

어떤 방식을 이용하면 시간을 줄일수 있을까요 ㅠㅠ

#include<iostream>
#include<vector>
#include<utility>
#include<stack>
using namespace std;

vector<vector<pair<int, int>>> adjLidt;
vector<bool> visit;
int N, M;
int l, r;
stack<int> st;

int main() {
	int u, v, Q, i, j, k;
	int cnt;
	int t, next, order;

	scanf("%d %d", &N, &M);

	adjLidt = vector<vector<pair<int, int>>>(N);

	for (i = 1; i <= M; i++) {
		scanf("%d %d", &u, &v);
		adjLidt[u - 1].push_back(make_pair(v - 1, i));
		adjLidt[v - 1].push_back(make_pair(u - 1, i));
	}

	scanf("%d", &Q);
	for (i = 0; i < Q; i++) {
		cnt = 0;
		scanf("%d %d",&l, &r);
		visit = vector<bool>(N, false);
		for (j = 0; j < N; j++) {
			if (visit[j] == false) {
				visit[j] = true;
				cnt++;
				st.push(j);
				while (!st.empty()) {
					t = st.top();
					st.pop();
					for (k = 0; k < adjLidt[t].size(); k++) {
						next = adjLidt[t][k].first;
						order = adjLidt[t][k].second;
						if ((order <l || r< order) && visit[next] == false ) {
							visit[next] = true;
							st.push(next);
						}
					}
				}
			}
		}
		printf("%d\n", cnt);
	}
}

dlwocks31 5년 전 1

dfs의 시간복잡도는 대략 O(E)고, 이걸 Q번 수행함으로 총 시간복잡도는 대략 O(EQ)고, EQ는 대략 6*10⁹임으로 당연히 시간초과가 납니다. 완전히 다른 알고리즘을 사용해야 합니다.

khx5558 5년 전 0

그럼 DFS로는 해결할 수 없는 문제라는 말씀이신가요..? ㅜㅜ
그렇다면 혹시 좀만 힌트라도 주실수 없나요 ㅜㅜ

dlwocks31 5년 전 1

단순한 dfs로는 힘들 것 같네요. 저도 능력이 부족해 감이 안잡히네요..ㅠ꽤 난이도 있는 문제인것 같습니다

khx5558 5년 전 0

감사합니다ㅜㅜ

더 생각해봐야겠네요 ㅜ

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

문제

문제

출처

ICPC

11897번 시간초과인데 고수님들 부탁드립니다 ㅜㅜ

khx5558 5년 전 0

dlwocks31 5년 전 1

khx5558 5년 전 0

dlwocks31 5년 전 1

khx5558 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말