풀이
n개의 노드에 대해, 각 노드의 degree가 주어진다.
주어진 입력에 맞게 그래프를 구성해서 간선들을 출력하는 문제이다.
(불가능한 경우는 주어지지 않는다)
남은 degree의 수가 가장 큰 노드를, 그 다음으로 작은 애들이랑 하나씩 이어주자.
이런 작업을 degree가 0이 될 때까지 반복하자.
다시 말해, degree가 큰 순서대로 먼저 간선을 이어주면 된다.
그럼 된다.
증명(?)
주어지는 그래프는 항상 valid한 그래프이다. 그럼, 완성된 그래프에서 노드를 하나씩 제거한다고 가정해보자. degree가 가장 큰 노드부터 제거해보자.
- 그래프 G에서 degree가 가장 큰 노드 하나를 제거해도, G’은 여전히 valid한 그래프이다.
- 마찬가지로 G’에 1의 작업을 반복해도, G’‘은 여전히 valid한 그래프이다.
- 이 작업을 노드 수가 0이 될 때까지 반복할 수 있다.
이제 간선들을 제거 하지 말고 추가 해보자.
띠용?!
코드
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
int n;
priority_queue<pii, vector<pii>, less<pii> > pq;
vector<int> r[501];
vector<pii> tmp;
int main() {
scanf("%d", &n);
for (int i = 1, x; i <= n; i++) {
scanf("%d", &x); pq.push({ x,i });
}
while (!pq.empty()) {
auto a = pq.top(); pq.pop();
while (a.first--) {
auto b = pq.top(); pq.pop();
r[a.second].push_back(b.second);
if (--b.first) tmp.push_back(b);
}
for (pii it : tmp) pq.push(it);
tmp.clear();
}
for (int i = 1; i <= n; i++) {
for (int j : r[i]) printf("%d %d\n", i, j);
}
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이