这两道题差不多，POJ这道我很久以前就做过，但是比赛的时候居然没想起来。。
POJ 这道题的题意是，N个王子每个人都有喜欢的公主，当他们选定一个公主结婚时，必须是的剩下的人也能找到他喜欢的公主结婚。
思路，首先对于王子，对于每一个他喜欢的公主，直接连边，然后再根据已经给出的匹配方案，建立公主->王子的边。
最后求出SCC后在同一强联通分量里的王子和公主就可以了。
代码就不贴了
下面再讲一下HDU 4685这道题，两道题的唯一区别就是，上一道题，每个公主到王子的匹配方案都是给出的，是一定存在的，那是因为公主和王子的个数是相同的。
但是这道题公主和王子的个数不同，就无法做到两两匹配，必然存在光棍的情况。
光棍其实挺正常的，但是对于这道题，我们就需要虚拟一些王子和公主出来。
一个王子没有匹配的话，那么虚拟一个公主出来，表示所有的王子都喜欢这个公主，同理虚拟出王子的情况。
那么在求出匹配之后，我们就可以根据这些匹配来建立公主->王子的边，然后操作就和上一题一样了。
代码：
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#define Max 2505
#define FI first
#define SE second
#define ll long long
#define PI acos(-1.0)
#define inf 0x3fffffff
#define LL(x) ( x << 1 )
#define bug puts("here")
#define PII pair<int,int>
#define RR(x) ( x << 1 | 1 )
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
using namespace std;
inline void RD(int &ret) {
char c;
int flag = 1 ;
do {
c = getchar();
if(c == '-')flag = -1 ;
} while(c < '0' || c > '9') ;
ret = c - '0';
while((c=getchar()) >= '0' && c <= '9')
ret = ret * 10 + ( c - '0' );
ret * flag ;
}
inline void OT(int a) {
if(a >= 10)OT(a / 10) ;
putchar(a % 10 + '0') ;
}
inline void OT(double a) {
char x[111] ;
sprintf(x , "%f" , a) ;
printf("%s
",x) ;
}
inline void RD(double &ret) {
char c ;
int flag = 1 ;
do {
c = getchar() ;
if(c == '-')flag = -1 ;
} while(c < '0' || c > '9') ;
ll fuck1 = c - '0' ;
while((c = getchar()) >= '0' && c <= '9') {
fuck1 = fuck1 * 10 + c - '0' ;
}
ll fuck2 = 1 ;
while((c = getchar()) >= '0' && c <= '9') {
fuck1 = fuck1 * 10 + c - '0' ;
fuck2 *= 10 ;
}
ret = flag * (double)fuck1 / (double)(fuck2) ;
}
/***************************************************/
#define N 2005
int n , m ;
int fk[N] ;
int vis[N] ;
struct kdq {
int s , e , next ;
} ed[N * N] ;
int head[N] , num = 0 ;
int nn ;
int linkx[N] ,linky[N] ;
vector<int>G[N] ;
void add(int s ,int e) {
ed[num].s = s ;
ed[num].e = e ;
ed[num].next = head[s] ;
head[s] = num ++ ;
}
int dfs(int now) {
int sz = G[now].size() ;
for (int i = 0 ; i < sz ; i ++ ) {
int e = G[now][i] ;
if(!vis[e]) {
vis[e] = 1 ;
if(linky[e] == -1 || dfs(linky[e])) {
linky[e] = now ;
linkx[now] = e ;
return 1 ;
}
}
}
return 0 ;
}
//tarjan_define
int low[N] , dfn[N] , st[N] , belong[N] ;
int top , dp ,SCC ;
void tarjan(int now) {
vis[now] = 1 ;
st[top ++ ] = now ;
dfn[now] = low[now] = dp ++ ;
for (int i = head[now] ; i != -1 ; i = ed[i].next ) {
int v = ed[i].e ;
if(dfn[v] == -1) {
tarjan(v) ;
low[now] = min(low[now] ,low[v]) ;
} else if(vis[v]) {
low[now] = min(low[now] ,dfn[v]) ;
}
}
if(low[now] == dfn[now]) {
int xx ;
SCC ++ ;
do {
xx = st[-- top ] ;
vis[xx] = 0 ;
belong[xx] = SCC ;
} while(xx != now) ;
}
}
//init
void init() {
mem(linkx ,-1) ;
mem(linky ,-1) ;
mem(vis, 0) ;
mem(low,0) ;
mem(dfn ,-1) ;
mem(st ,0) ;
mem(head ,-1) ;
num = top = dp = SCC = 0 ;
}
int main() {
int T ;
#ifndef ONLINE_JUDGE
freopen("D:\fuck.txt","r",stdin) ;
#endif
cin >> T ;
int ca = 0 ;
while(T -- ) {
RD(n) ;
RD(m) ;
int nfk = max(m , n) ;
init() ;
for (int i = 0 ; i <= N >> 1 ; i ++ ) {
G[i].clear() ;
}
REP(i , 1 , n ) {
int x ;
RD(x) ;
while(x -- ) {
int y ;
RD(y) ;
add(i , nfk + y) ;
G[i].push_back(nfk + y) ;
}
}
nn = 0 ;
for (int i = 1 ; i <= nfk ; i ++ ) {
mem(vis ,0) ;
nn += dfs(i) ;
}
nn = 2 * nfk ;
for (int i = 1 ; i <= nfk ; i ++ ) { //虚拟公主
if(linkx[i] == -1) {
linkx[i] = ++ nn ;
linky[nn] = i ;
for (int j = 1 ; j <= nfk ; j ++ ) { //所有王子都喜欢这个公主
add(j , nn) ;
}
}
add(linkx[i] , i) ;
}
for (int i = nfk + 1 ; i <= nfk << 1 ; i ++ ) { //虚拟王子
if(linky[i] == -1) {
linkx[++ nn] = i ;
linky[i] = nn ;
for (int j = nfk + 1 ; j <= nfk + nfk ; j ++ ) { //这个王子喜欢所有公主
add(nn , j) ;
}
}
add(i , linky[i]) ;
}
mem(vis, 0) ;
for (int i = 1 ; i <= nn ; i ++ ) {
if(dfn[i] == -1)tarjan(i) ;
}
printf("Case #%d:
",++ ca) ;
set<int>fk ;
__typeof(fk.begin()) it ;
for (int i = 1 ; i <= n ; i ++ ) {
fk.clear() ;
for (int j = head[i] ; ~j ; j = ed[j].next ) {
int x = belong[i] ;
int y = belong[ed[j].e] ;
if(x == y && ed[j].e <= nfk + m) {
fk.insert(ed[j].e - nfk) ;
}
}
printf("%d",fk.size()) ;
for (it = fk.begin() ; it != fk.end() ; it ++) {
printf(" %d",*it) ;
}
puts("") ;
}
}
return 0 ;
}