글 읽기 - 효율적인 방법!!

sotter1020 5년 전 0

문제는 풀었는데 효율적인 방법이 있을까요?

O(n^3)인거 같은데..

좀 더 간단히 할 수 있을거 같은데 방법이 안떠오르네요 ㅠㅠ;

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> adj[32000 + 1];
bool visited[32000 + 1];
int indegree[32000 + 1];
vector<int> order[32000 + 1];
int n, m;

void orderingQuestion() {
	queue<int> q;
	for (int l = 0; l < n; ++l) {
		for (int i = 1; i <= n; ++i) 
			if (!visited[i] && indegree[i] == 0) {
				visited[i] = true;
				q.push(i);
				break;
			}

		while (!q.empty()) {
			int prere = q.front();
			cout << prere << ' ';
			q.pop();
			for (int i = 0; i < adj[prere].size(); ++i)
				if (!visited[adj[prere][i]]) {
					indegree[adj[prere][i]]--;
				}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int prere, next;
		cin >> prere >> next;
		adj[prere].push_back(next);
		indegree[next]++;
	}

	orderingQuestion();

	return 0;
}

djm03178 5년 전 0

17번째 줄과 같은 루프를 돌리는 대신에 우선순위 큐를 사용하면 NlogN에 수행이 가능합니다.

그리고 이 코드의 복잡도는 세제곱은 아니고 N^2 + M인 것 같네요.

sotter1020 5년 전 0

아! 감사합니다!

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

문제

문제

출처

ICPC

효율적인 방법!!

sotter1020 5년 전 0

djm03178 5년 전 0

sotter1020 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말