B. Lazy Student

Graph, MST


출처: Codeforces B. Lazy Student

SOL)

MST에 포함된 간선은 1이 아닌 -1로 바꿔준 뒤
가중치를 기준으로 소팅을 한다.
이러면 가중치가 같은것들 중 MST에 포함된 녀석들이
앞에 위치하게 된다.

이제 하나씩 살펴 보는데 만약 MST에 포함된 간선일 경우
무조건 정점 1에 연결을 시킨다.
(이때가 최악의? MST를 고려하는 상황이다.)
그러면 하나 씩 연결될 때마다 0, 1, 2, 3, ....
이런 식으로 빈 공간이 생성된다.
예를 들어 1->2, 1->3을 연결했다 가정하면
2->3으로 연결할 수 있는 공간이 1개 발생한다는 것이다.

만약 이 공간이 하나도 없는데 공간이 필요하면 답은 -1
공간이 있으면 채워가면 된다.
{(2,3)}, {(2,4), (3,4)}, {(2,5), (3,5), (4,5)}.. 요런식으로 빈공간을 채웠다.



[-] Collapse

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

pair<pair<int, int>, int> edge[100010];
pair<int, int> ans[100010];
int main(){
    //freopen("input.txt", "r", stdin);
    int n, m; scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++){
        scanf("%d %d", &edge[i].first.first, &edge[i].first.second);
        edge[i].first.second *= -1;
        edge[i].second = i;
    }
    sort(edge, edge + m);

    bool check = true;
    long long empty = 0, filled = 0;
    long long count = -1;
    int u = 1, v = 2;
    int n_u = 2, n_v = 3;
    for (int i = 0; i < m; i++){
        int idx = edge[i].second;
        if (edge[i].first.second == -1){
            ans[idx].first = u;
            ans[idx].second = v++;
            count++;
            empty += count;
        }
        else{
            if (empty - filled <= 0){
                check = false;
                break;
            }
            else{
                filled++;
                ans[idx].first = n_u++;
                ans[idx].second = n_v;
                if (n_u == n_v){
                    n_u = 2;
                    n_v++;
                }
            }
        }
    }

    if (!check) printf("-1");
    else for (int i = 0; i < m; i++) printf("%d %d\n", ans[i].first, ans[i].second);
    return 0;
}