CF 847 L - Berland SU Computer Network
問題
問題概要
台のルータがあり、何台かはコードで繋がれており、ネットワークを構成している。ルータの構造は木である。次のような情報が与えられるので、元のネットワークの構造を復元せよ:
それぞれのコードとと直接繋がっているルータに対して、を通じてと反対側にあるルータが何であるかが与えられる(つまり、から見た時のそれぞれの部分木の情報が分かる)。
妥当な復元が存在しない時は-1
と答えよ。
- 各リストについて、要素数は個でdistinct、個目のリストには入っていない
アイデア
まず、-1
になる状況を考える。与えられるリストの形式から、どれを繋いでいるかは分からないまでも辺の個数を見ることが出来る。それを見て、個になっていなければおかしい。
辺の個数が妥当だと確認できたところで、復元をはじめていく。復元の方法としては、で全点対に対して注目をして、「その2点間()に実際に辺がある ⇒ から見た時にを含んでいる集合のsize + から見た時にを含んでいる集合の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; }