AOJ : 2011 - Gather the Maps!
問題概要
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2011&lang=jp
問題文が日本語なので省略です
アルゴリズム
次のサイトの方が、図つきでわかりやすく説明してくれているので、こちらのサイトを参考にしてください。
http://www.deqnotes.net/acmicpc/p0017/
プログラム
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); if(n == 0) break; ArrayList<HashSet<Integer>> set = new ArrayList<HashSet<Integer>>(); boolean[][] flg = new boolean[n][32]; for(int i=0;i<n;i++){ set.add(new HashSet<Integer>()); set.get(i).add(i); int m = sc.nextInt(); for(int j=0;j<m;j++){ int x = sc.nextInt(); flg[i][x-1] = true; } } int ans = 0; for(;ans<30;ans++){ HashSet<Integer> tmp = new HashSet<Integer>(); for(int j=0;j<n;j++){ if(flg[j][ans]){ tmp.addAll(set.get(j)); } } if(tmp.size() == n) break; for(int j=0;j<n;j++){ if(flg[j][ans]){ set.get(j).addAll(tmp); } } } System.out.println(ans==30 ? -1 : ans+1); } } }