USACO 2018 US Open Gold 2 - Milking Order

 USACO 2018 US Open Gold 2번이다. BOJ 15758번에 등록되어 있으며 문제는 여기서 볼 수 있다.

문제 설명

첫 줄에 n과 m이 주어진다. n는 소의 숫자이며, m은 세트의 숫자이다. 다음 m개의 줄에 한 세트씩 입력이 들어온다. 한개의 세트에 대한 입력은 k와 k개의 숫자로 구성된다. k개의 숫자는 소들의 순서관계이다. 우리는 위에서부터 최대한 많이 순서를 지켜서 소들을 정렬 시키려고 한다. 순서가 상관없는 소들에 대해서는 숫자가 작은 소를 우선으로 정렬한다. 이때 위에서 부터 지킬 수 있는 조건의 갯수와 그 정렬방법을 출력해야 한다. 

문제 풀이 

문제를 보자 마자 바로 떠오르는 개념이 있다. "위상정렬". 위에서 부터 최대 몇 개까지의 조건을 지킬 수 있는지를 알 수 있다면 Priority_Queue를 이용한 위상정렬로 소들의 순서를 구할 수 있을 것이다. 따라서 최대 몇 개까지의 조건에 대해서 위상정렬이 가능한지에 대해서 구하면 된다. 
조건이 계속 쌓이는 것에 대해서 생각해보자. 일정 시점에서 위상정렬이 가능하다면 이 전의 모든 시점에서는 위상정렬이 가능했을 것이다. 어떤 시점에서 위상정렬이 불가능하면 그 이후의 모든 시점에서 위상정렬은 불가능하다. 따라서 Parametric Search를 이용하면 어느 시점까지 위상정렬이 가능한지를 Log m 번만에 알 수 있다. 위상정렬을 할 때마다 적용되는 순서를 모두 확인해주어야 하므로 시간복잡도는 m이다.
따라서 총 O(M lg M) 만에 문제를 해결할 수 있다. 

코드

 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
vector<ll> v[101010];
vector<ll> edg[101010];
 
ll i,j,k,l,m,n;
ll cyc;
ll cnt[101010];
 
 
bool f(ll x){
    cyc=0;
    for(i=1;i<=n;i++){
        edg[i].clear();
        cnt[i]=0;
    }
    for(i=1;i<=x;i++){
        for(j=1;j<v[i].size();j++){
            edg[ v[i][j-1] ].push_back(v[i][j]);
            cnt[v[i][j]]++;
        }
    }
    priority_queue<ll> pq;
    for(i=1;i<=n;i++){
        if(cnt[i]==0) pq.push(i);
    }
    while(!pq.empty()){
        cyc++;
        ll q=pq.top(); pq.pop();
        for(auto y:edg[q]){
            cnt[y]--;
            if(cnt[y]==0){
                pq.push(y);
            }
        }
    }
 
    if(cyc==n) return false;
    else return true;
}
 
int main(){
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%lld",&k);
        for(j=1;j<=k;j++){
            scanf("%lld",&l);
            v[i].push_back(l);
        }
    }
 
    ll lo=-1;
    ll hi=m;
    ll mid;
    while(lo<hi){
        mid=(lo+hi)/2;
        if(f(mid)){
            hi=mid;
        }
        else lo=mid+1;
        //printf("%lld %lld %lld\n",lo,hi,mid);
    }
    k=lo-1;
 
    for(i=1;i<=n;i++){
        edg[i].clear();
        cnt[i]=0;
    }
    for(i=1;i<=k;i++){
        for(j=1;j<v[i].size();j++){
            edg[ v[i][j-1] ].push_back(v[i][j]);
            cnt[v[i][j]]++;
        }
    }
    priority_queue<ll,vector<ll>,greater<ll>> pq;
    for(i=1;i<=n;i++){
        if(cnt[i]==0) pq.push(i);
    }
    while(!pq.empty()){
        ll q=pq.top(); pq.pop();
        printf("%lld ",q);
        for(auto y:edg[q]){
            cnt[y]--;
            if(cnt[y]==0){
                pq.push(y);
            }
        }
    }
}