불러오는 중
N개의 정수로 이루어진 차수 수열이 주어진다. 이 차수 수열을 갖는 단순 그래프(무방향 그래프이며, 자기 간선과 다중 간선이 없는 그래프)를 구성하라. 구성이 불가능하다면 -1을 출력하라.
차수 수열이 단순 그래프로 구성 가능한지 판별하기 위해 Erdős-Gallai 정리를 활용하라. Erdős-Gallai 정리에 따르면, 차수 수열을 내림차순으로 정렬한 d1≥d에 대해 모든 ()에 대하여 다음 부등식을 만족하는 경우에만 단순 그래프로 구성할 수 있다.
∑i=1kdi≤k(k−1)+∑i=k+1Nmin(di,k)
첫째 줄에 정점의 수 N이 주어진다.
둘째 줄에 각 정점의 차수를 나타내는 N개의 정수가 공백으로 구분되어 주어진다.
주어진 차수 수열로 단순 그래프를 구성할 수 있다면, 첫째 줄에 간선의 수 M을 출력한다. 둘째 줄부터 M개의 줄에 걸쳐 각 간선의 양 끝 정점 번호 u와 v를 공백으로 구분하여 출력한다. 간선의 출력 순서와 정점의 출력 순서는 상관없다. 모든 정점의 차수가 0이어서 간선이 하나도 없는 경우, 첫째 줄에 0만 출력한다.
그래프를 구성할 수 없다면 첫째 줄에 -1을 출력한다.
4
3 3 3 3
6
1 2
1 3
1 4
2 3
2 4
3 4
3
3 2 1
-1