PKU 1419 Graph Coloring
はてなグループの方に書くとあれかなと思ったので使い分けつつ行こうかと思います。
http://poj.org/problem?id=1419
多分簡単な問題。
グラフのノードを白黒に塗るが、黒はお互いにエッジでつながれてはいけない。
その時黒の個数を最大にするときの黒いノード番号を出力。
始点をn通り試して幅優先した。グラフが連結でないかとか心配したけど大丈夫でした。
main(){ int m; cin>>m; while(m--){ int n,k; cin>>n>>k; vector<int> gra[n]; rep(i,k){ int a,b; cin>>a>>b; --a,--b; gra[a].pb(b); gra[b].pb(a); } vector<int> ans; rep(i,n){ int col[n]; memset(col,0,sizeof(col)); queue<int> Q; Q.push(i); while(!Q.empty()){ int v=Q.front();Q.pop(); if(col[v])continue; int bl=0; rep(i,gra[v].size()){ int to=gra[v][i]; if(col[to]==2)bl++; if(col[to])continue; Q.push(to); } if(bl==0)col[v]=2; else col[v]=1; } vector<int> tans; rep(i,n)if(col[i]==2)tans.pb(i); if(tans.size()>ans.size())ans=tans; } sort(ALL(ans)); cout<<ans.size()<<endl; rep(i,ans.size()){ if(i)cout<<" "; cout<<ans[i]+1; } cout<<endl; } }