글 읽기 - 시간복잡도 질문입니다

kengh2472 5년 전 0

2458번 키순서 문제에서 원하는 풀이 방향은 플로이드 워셜인 것 같지만 혹시나 하는 마음에 정방향 역방향 그래프를 2개만들어 bfs로 점을 찾아 더한값이 N-1과 같다면 정답값을 +1 하는 방식으로 풀었습니다. 시간초과를 기대한것과 달리 통과를 하였는데 시간복잡도를 계산해보았습니다.

76번째 줄 func(1) + func(2)에서 O(2M) N만큼 돌리니 O(2MN)

2MN == N^3 == 125,000,000 이라서 시간1초 언저리라 가능.

이렇게 시간복잡도를 계산해도 될까요?

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

#define INF 987654321

int N, M, visit[501];
vector<int> v1[501], v2[501];
//visit배열 초기화
void reset() {
	for (int i = 1; i <= N; i++)
		visit[i] = 0;
}

//정방향
int func1(int st) {
	int sum = 0;
	queue<int> q;
	q.push(st);

	while (!q.empty()) {
		int fr = q.front();
		q.pop();
		visit[fr] = 1;
		for (int i = 0; i < v1[fr].size(); i++) {
			if(visit[v1[fr][i]] == 0){
				q.push(v1[fr][i]);
				sum++;
				visit[v1[fr][i]] = 1;
			}
		}

	}
	reset();
	return sum;
}

//역방향
int func2(int st) {
	int sum = 0;
	queue<int> q;
	q.push(st);

	while (!q.empty()) {
		int fr = q.front();
		q.pop();
		visit[fr] = 1;
		for (int i = 0; i < v2[fr].size(); i++) {
			if (visit[v2[fr][i]] == 0) {
				q.push(v2[fr][i]);
				sum++;
				visit[v2[fr][i]] = 1;
			}
		}

	}
	reset();
	return sum;
}

int main(void) {
	scanf("%d %d", &N, &M);

	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		v1[a].push_back(b);
		v2[b].push_back(a);
	}

    //개수 카운트
	int output = 0;
	for (int i = 1; i <= N; i++) {
		if (func1(i) + func2(i) == N - 1)
			output++;
	}

	printf("%d", output);

	return 0;
}

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

문제

문제

출처

ICPC

시간복잡도 질문입니다

kengh2472 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말