裏紙

ほぼ競プロ、たまに日記

CF 847 L - Berland SU Computer Network

問題

Problem - L - Codeforces

問題概要

n台のルータがあり、何台かはコードで繋がれており、ネットワークを構成している。ルータの構造は木である。次のような情報が与えられるので、元のネットワークの構造を復元せよ:

それぞれのコードppと直接繋がっているルータiに対して、pを通じてiと反対側にあるルータが何であるかが与えられる(つまり、iから見た時のそれぞれの部分木の情報が分かる)。

妥当な復元が存在しない時は-1と答えよ。

  •  2 \le n \le 1000
  • 各リストについて、要素数n-1個でdistinct、i個目のリストにiは入っていない

イデア

まず、-1になる状況を考える。与えられるリストの形式から、どれを繋いでいるかは分からないまでも辺の個数を見ることが出来る。それを見て、2(n-1)個になっていなければおかしい。

辺の個数が妥当だと確認できたところで、復元をはじめていく。復元の方法としては、O(n^2)で全点対に対して注目をして、「その2点間(a,b)に実際に辺がある ⇒ aから見た時にbを含んでいる集合のsize + bから見た時にaを含んでいる集合のsize がnに一致する」ということに注目して、辺を復元していき、最終的にそれが木になっているかを確認すればよい。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str + sep);
    string buffer;
    while( getline(ss,buffer,sep ) ) v.pb(buffer);
    return v;
}

set<int> cv(const string &str){
    vector<string> t = split(str, ':');
    set<int> ret;
    for(const auto &x:split(t[1], ',')){
        ret.insert(atoi(x.c_str())-1);
    }
    return ret;
}

const int N = 1000;
vector<int> G[N];

void solve(){
    int n;
    cin >>n;

    int e_sum = 0;
    vector<vector<set<int>>> r(n);
    vector<vector<int>> idx(n,vector<int>(n,-1));
    rep(i,n){
        string s;
        cin >>s;
        for(string t:split(s, '-')) r[i].pb(cv(t));

        rep(j,r[i].size()){
            for(int v:r[i][j]) idx[i][v] = j;
        }
        e_sum += r[i].size();
    }

    if(e_sum != 2*(n-1)){
        cout << "-1" << endl;
        return;
    }

    int edge = 0;
    rep(i,n)rep(j,i){
        if(r[i][idx[i][j]].size() + r[j][idx[j][i]].size() == n){
            ++edge;
            G[i].pb(j);
            G[j].pb(i);
        }
    }

    vector<bool> vis(n);
    vis[0]=true;
    queue<int> que;
    que.push(0);
    while(!que.empty()){
        int now = que.front();
        que.pop();
        for(int e:G[now]){
            if(!vis[e]){
                vis[e] = true;
                que.push(e);
            }
        }
    }

    bool connected = true;
    rep(i,n)if(!vis[i]) connected = false;

    if(!connected || edge != n-1){
        cout << "-1" << endl;
        return;
    }
    cout << n-1 << endl;
    rep(i,n){
        for(int j:G[i])if(i<j) cout << i+1 << " " << j+1 << endl;
    }
}

int main(){
    solve();
    return 0;
}