2011-Gather the Maps!
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2011&lang=jp
UnionFindを使って解いてしまいWAった。
考え方
各人が持ちうるマップを求めていく。
実装(C++)
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <climits> #include <cctype> #include <ctime> #include <cassert> #include <cwchar> #include <cstdarg> #include <cwctype> #include <queue> #include <stack> #include <algorithm> #include <list> #include <vector> #include <set> #include <map> #include <iostream> #include <deque> #include <complex> #include <string> #include <functional> #include <iomanip> #include <tr1/unordered_map> #include <boost/foreach.hpp> #define foreach BOOST_FOREACH using namespace std; using namespace tr1; using namespace boost; typedef long long int lli; typedef unsigned int uint; int main(){ int n; for(;(cin>>n),n;){ vector<int> free[31]; vector<lli> gathered(n); for(int i=0;i<n;i++){ int k,t; cin>>k; for(;k--;){ cin>>t; free[t].push_back(i); } gathered[i]=1LL<<i; } bool NA=true; for(int i=1;i<=30;i++){ for(int j=0;j<(int)free[i].size();j++){ for(int k=0;k<(int)free[i].size();k++){ gathered[free[i][j]]|=gathered[free[i][k]]; } } bool check=false; for(int j=0;j<n;j++){ if(gathered[j]==(1LL<<n)-1)check=true; } if(check){ NA=false; cout<<i<<endl; break; } } if(NA){ cout<<-1<<endl; } } return 0; }