[BOJ][C/C++] 1766번 : 문제집

🔗링크

1. 문제 풀이

우선 문제들에 조건을 읽어보면
2. 우선순위를 나타내는 순서쌍 (v,u)를 만족 시켜야 하고
3. v의 값이 낮은 순으로 풀어야 한다.

즉 우선순위 큐와 위상정렬을 이용하면 풀이가 가능하다.

---

예제 입력으로 예를 들어보자
입력 순서쌍으로 그래프를 그려본다면 다음과 같아진다.

여기서 진입차수가 0인 문제는 선행 문제가 없다는 것이기에 제거가 가능하고
난이도를 고려해야 하니 3번 문제를 제거한다.

---

제거된 문제를 선행 문제로 가지고 있던 문제들은 진입차수 - 1을 해준다.
이후 제거 가능한 후보들을 갱신한다.

---

이를 반복하면 위상정렬이 가능하다.

---

2. 코드

#include <stdio.h>
#include<vector>
using namespace std;

int N, M, in[32001], hs, heap[32010];
vector<int> out[32001];

void push(int v) {
	int i = ++hs;
	for (; i > 1 && heap[i / 2] > v; i /= 2)
		heap[i] = heap[i / 2];
	heap[i] = v;
}

int pop() {
	int p = 1, c = 2, tmp = heap[hs], res = heap[1];
	hs--;
	while (c <= hs) {
		if (c < hs && heap[c] > heap[c + 1])c++;
		if (heap[c] > tmp)break;
		heap[p] = heap[c];
		p = c;
		c *= 2;
	}
	heap[p] = tmp;
	return res;
}


void f() {
	int cur;
	while (hs) {
		cur = pop();
		printf("%d ",cur);
		for (int i = 0; i < out[cur].size(); i++) {
			in[out[cur][i]]--;
			if (in[out[cur][i]] == 0)push(out[cur][i]);
		}
	}
}


int main(){
	int v, u;
	scanf("%d %d",&N,&M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &v, &u);
		out[v].push_back(u);
		in[u]++;
	}
	for (int i = 1; i <= N; i++)if (in[i] == 0)push(i);
	if (N == 1)printf("1");
	else f();
	return 0;
}

3. 후기

포스팅 꾸준히 하기
설명 대충하지 말기