实现算法greedySetCover

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description


实现集合覆盖问题的近似算法greedySetCover。

Input

输入数据的第一行有2 个正整数n 和m(n<10000,m<10000),分别表示有限集X 中元素个数和子集族F 中子集个数。X = {0,1,, n -1},F= {f0 ,f1 ,…… ,fm-1 } 。接下来的m行中,每行对应于F中一个子集 fi。第一个数是子集 fi 中元素个数ki ,接着的ki 个数表示 fi 中的元素。

Output

将计算出的最小覆盖子集输出。第1 行是最小覆盖子集数。第2 行是最小覆盖子集。

Sample Input

12 6
6 0 1 2 3 4 5
4 0 3 6 9
4 1 4 7 10
4 4 5 7 8
4 2 5 8 11
2 9 10

Sample Output

4
0 4 2 1

Hint

 

Source