Description
Once upon a time there lived a king and he had N sons. And there were N beautiful girls in the kingdom and the king knew about each of his sons which of those girls he did like. The sons of the king were young and light-headed, so it was possible for one son to like several girls.
So the king asked his wizard to find for each of his sons the girl he liked, so that he could marry her. And the king's wizard did it -- for each son the girl that he could marry was chosen, so that he liked this girl and, of course, each beautiful girl had to marry only one of the king's sons.
However, the king looked at the list and said: "I like the list you have made, but I am not completely satisfied. For each son I would like to know all the girls that he can marry. Of course, after he marries any of those girls, for each other son you must still be able to choose the girl he likes to marry."
The problem the king wanted the wizard to solve had become too hard for him. You must save wizard's head by solving this problem.
Input
The first line of the input contains N -- the number of king's sons (1 <= N <= 2000). Next N lines for each of king's sons contain the list of the girls he likes: first Ki -- the number of those girls, and then Ki different integer numbers, ranging from 1 to N denoting the girls. The sum of all Ki does not exceed 200000.
The last line of the case contains the original list the wizard had made -- N different integer numbers: for each son the number of the girl he would marry in compliance with this list. It is guaranteed that the list is correct, that is, each son likes the girl he must marry according to this list.
Output
Output N lines.For each king's son first print Li -- the number of different girls he likes and can marry so that after his marriage it is possible to marry each of the other king's sons. After that print Li different integer numbers denoting those girls, in ascending order.
Sample Input
4
2 1 2
2 1 2
2 2 3
2 3 4
1 2 3 4
Sample Output
2 1 2
2 1 2
1 3
1 4 題目大意：有n個王子 和 n個美人 ， 一個王子可以喜歡幾個美人，但是一個美人只能嫁一個王子，同時，一個王子也只能娶一個自己喜歡的美人。問：對於每個王子來說，他可以娶哪幾個美人為妻，並且使其他王子也能娶到自己喜歡的美人。 解題思路：這道題初看像二部圖，但是按此思路想找不到解決辦法。想想輸入最後一行給出的一個完美匹配，應該有它的用處。 先說一下如何建圖：將每個王子u 和 他喜歡的美人 v 之間連一條有向邊<u , v + n>(為避免頂點的序號混淆,將 美人的序號 +n 作為美人頂點的序號)，最後，通過輸入中給出的一個完美匹配，將美人 v 與自己暫時的丈夫 u 之間連一條有向邊<v + n , u>，建圖完畢。 然後，用tarjan求強連通分量，題目中樣例建圖如下，其中黑色邊代表王子喜歡美人，紅色邊代表輸入中給出的一個完美匹配 ：
從圖中可以看出，每個強連通分量中頂點的個數都是偶數，每個王子可以與同自己喜歡的並且在一個強連通分量中的美人結婚，例如：如果 1 可以與 6 結婚，那麼2 就會與5 結婚；如果1 與 5 結婚 ， 那麼2 就會與 6 結婚 ；這兩種方式均不影響3 和 4 。 請看代碼:
<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<set>
#include<vector>
#define mem(a , b) memset(a , b , sizeof(a))
using namespace std ;
const int MAXN = 4005 ;
vector<int> vert[MAXN] ; // 頂點
vector<int> fz[MAXN] ; // 記錄每個強連通分量中的頂點
int ans[MAXN] ;
int n , m ;
bool vis[MAXN] ;
int dfn[MAXN] ;
int low[MAXN] ;
int id[MAXN] ;
int stap[MAXN] ;
int top ;
bool inq[MAXN] ;
int tmpdfn ;
int sumf ; // 記錄強連通分量個數
bool bi[MAXN] ;
inline void RD(int &a)
{
a = 0 ;
char t ;
do
{
t = getchar();
}
while(t < '0' || t > '9') ;
a = t - '0';
while((t = getchar()) >= '0' && t <= '9')
a = a * 10 + ( t - '0' );
}
inline void OT(int a)
{
if(a >= 10)
OT(a / 10) ;
putchar(a % 10 + '0') ;
}
void clr()
{
mem(vis , 0) ;
mem(dfn , 0) ;
mem(low , 0) ;
mem(fz , 0) ;
mem(inq , 0) ;
mem(stap , -1) ;
mem(id , -1) ;
top = -1 ;
tmpdfn = 0 ;
sumf = 0 ;
int i ;
for(i = 0 ; i <= n * 2 ; i ++)
{
vert[i].clear() ;
fz[i].clear() ;
}
}
void tarjan(int u)
{
vis[u] = 1 ;
dfn[u] = low[u] = ++ tmpdfn ;
stap[++ top] = u ;
inq[u] = true ;
int i ;
for(i = 0 ; i < vert[u].size() ; i ++)
{
int v = vert[u][i] ;
if(!vis[v])
{
tarjan(v) ;
low[u] = min(low[u] , low[v]) ;
}
else if(inq[v])
low[u] = min(low[u] , dfn[v]) ;
}
if(dfn[u] == low[u])
{
int tmp ;
sumf ++ ;
do
{
tmp = stap[top --] ;
inq[tmp] = false ;
id[tmp] = sumf ;
fz[sumf].push_back(tmp) ;
}
while (tmp != u) ;
}
}
void init()
{
clr() ;
int i ;
int j ;
int b ;
for(i = 1 ; i <= n ; i ++)
{
int k ;
RD(k) ;
for(j = 0 ; j < k ; j ++)
{
RD(b) ;
vert[i].push_back(b + n) ;
}
}
for(i = 1 ; i <= n ; i ++)
{
int b ;
RD(b) ;
vert[b + n].push_back(i) ;
}
}
void solve()
{
int i ;
for(i = 1 ; i <= n ; i ++)
{
if(!vis[i])
{
tarjan(i) ;
}
}
int j ;
int k ;
for(i = 1 ; i <= n ; i ++)
{
int x = id[i] ;
mem(bi , 0) ;
int tp ;
for(j = 0 ; j < fz[x].size() ; j ++)
{
tp = fz[x][j] ;
bi[tp] = true ;
}
int p = 0 ;
for(j = 0 ; j < vert[i].size() ; j ++)
{
tp = vert[i][j] ;
if(bi[tp])
ans[p ++] = tp ;
}
sort(ans , ans + p) ;
OT(p) ;
if(p > 0)
putchar(' ') ;
for(j = 0 ; j < p ; j ++)
{
OT(ans[j] - n) ;
if(j < p - 1)
putchar(' ') ;
}
putchar('\n') ;
}
}
int main()
{
while (scanf("%d" , &n ) != EOF)
{
getchar() ;
init() ;
solve() ;
}
return 0 ;
}
</SPAN>
