http://poj.org/problem?id=1904
看到此题，似乎成了一个二分图，也许会往二分图算法上去思考，但是最后巫师的匹配数据让我疑惑，为什么要给你这个数据？
将巫师给你的数据作为每个王子的根节点，指向每个王子喜欢的其他女子，这时两点间路径的意义为可以替换的意思，那么即使有向图一定存在强连通分支，那么强联通分支内的所有节点都可以互相代替，所以只需要查找每个王子的根节点所在的强连通分支内有多少个他喜欢的女孩即可。
对输入和输出用putchar和getchar,并且用g++提交时间可以提高到480MS，如果用c++提交scanf和printf，则需要3+s左右。
putchar和getchar代码：
View Code
1 #include <stdio.h>
2 #include <string>
3 #include <algorithm>
4 using namespace std;
5 #define N 2001
6 #define NUM 200001
7 struct node
8 {
9 int num;
10 node *next;
11 }girl[NUM],*son[N],*p;
12 struct NODE
13 {
14 int end;
15 NODE *next;
16 }edge[NUM],*head[N],*q;
17 int num,cnt,father;
18 int root_stack[N],stack[N],init[N],belong[N],wife[N],cnt_girl[N];
19 void add(int soner,int girler)
20 {
21 p->num=girler;
22 p->next=son[soner];
23 son[soner]=p++;
24 }
25 void bulid(int soner,int girler)
26 {
27 for(node*tmp=son[soner];tmp;tmp=tmp->next)
28 if(tmp->num!=girler)
29 {
30 q->end=tmp->num;
31 q->next=head[girler];
32 head[girler]=q++;
33 }
34 }
35 void Gabow(int key)
36 {
37 root_stack[++root_stack[0]]=stack[++stack[0]]=key;
38 init[key]=++cnt;
39 for(NODE*tmp=head[key];tmp;tmp=tmp->next)
40 {
41 if(!init[tmp->end])
42 Gabow(tmp->end);
43 else if(!belong[tmp->end])
44 while(init[root_stack[root_stack[0]]]>init[tmp->end])
45 --root_stack[0];
46 }
47 if(root_stack[root_stack[0]]==key)
48 {
49 --root_stack[0],++father;
50 do
51 belong[stack[stack[0]]]=father;
52 while(stack[stack[0]--]!=key);
53 }
54 }
55 int getint()
56 {
57 int ret=0;
58 for(char c=getchar();isdigit(c);c=getchar())
59 ret=ret*10+c-48;
60 return ret;
61 }
62 void putint(int x)
63 {
64 if(x>9)
65 putint(x/10);
66 putchar(x%10+48);
67 }
68 int main()
69 {
70 num=getint();
71 p=girl;
72 for(int i=1,cnter;i<=num;++i)
73 {
74 cnter=getint();
75 for(int j=0,tmp;j<cnter;++j)
76 {
77 tmp=getint();
78 add(i,tmp);
79 }
80 }
81 q=edge;
82 for(int i=1;i<=num;++i)
83 {
84 wife[i]=getint();
85 bulid(i,wife[i]);
86 }
87 cnt=father=0;
88 for(int i=1;i<=num;++i)
89 if(!init[i])
90 Gabow(i);
91 for(int i=1,j=0;i<=num;++i,j=0)
92 {
93 cnt_girl[j++]=wife[i];
94 for(node*tmp=son[i];tmp;tmp=tmp->next)
95 if(belong[wife[i]]==belong[tmp->num]&&tmp->num!=wife[i])
96 cnt_girl[j++]=tmp->num;
97 putint(j);
98 sort(cnt_girl,cnt_girl+j);
99 for(int m=0;m<j;++m)
100 {
101 putchar(' ');
102 putint(cnt_girl[m]);
103 }
104 putchar('\n');
105 }
106 return 0;
107 }
scanf和printf代码：
View Code
1 #include <stdio.h>
2 #include <memory.h>
3 #include <algorithm>
4 using namespace std;
5 #define N 2001
6 #define NUM 200001
7 struct node
8 {
9 int num;
10 node *next;
11 }girl[NUM],*son[N],*p;
12 struct NODE
13 {
14 int end;
15 NODE *next;
16 }edge[NUM],*head[N],*q;
17 int num,cnt,father;
18 int root_stack[N],stack[N],init[N],belong[N],wife[N],cnt_girl[N];
19 void add(int soner,int girler)
20 {
21 p->num=girler;
22 p->next=son[soner];
23 son[soner]=p++;
24 }
25 void bulid(int soner,int girler)
26 {
27 for(node*tmp=son[soner];tmp;tmp=tmp->next)
28 if(tmp->num!=girler)
29 {
30 q->end=tmp->num;
31 q->next=head[girler];
32 head[girler]=q++;
33 }
34 }
35 void Gabow(int key)
36 {
37 root_stack[++root_stack[0]]=stack[++stack[0]]=key;
38 init[key]=++cnt;
39 for(NODE*tmp=head[key];tmp;tmp=tmp->next)
40 {
41 if(!init[tmp->end])
42 Gabow(tmp->end);
43 else if(!belong[tmp->end])
44 while(init[root_stack[root_stack[0]]]>init[tmp->end])
45 --root_stack[0];
46 }
47 if(root_stack[root_stack[0]]==key)
48 {
49 --root_stack[0],++father;
50 do
51 belong[stack[stack[0]]]=father;
52 while(stack[stack[0]--]!=key);
53 }
54 }
55 void ini()
56 {
57 root_stack[0]=stack[0]=0;
58 memset(init,0,sizeof(init));
59 memset(belong,0,sizeof(belong));
60 memset(wife,0,sizeof(wife));
61 memset(head,NULL,sizeof(head));
62 memset(son,NULL,sizeof(son));
63 }
64 int main()
65 {
66 while(scanf("%d",&num)==1)
67 {
68 p=girl;
69 for(int i=1,cnter;i<=num;++i)
70 {
71 scanf("%d",&cnter);
72 for(int j=0,tmp;j<cnter;++j)
73 {
74 scanf("%d",&tmp);
75 add(i,tmp);
76 }
77 }
78 q=edge;
79 for(int i=1;i<=num;++i)
80 {
81 scanf("%d",&wife[i]);
82 bulid(i,wife[i]);
83 }
84 cnt=father=0;
85 for(int i=1;i<=num;++i)
86 if(!init[i])
87 Gabow(i);
88 for(int i=1,j=0;i<=num;++i,j=0)
89 {
90 cnt_girl[j++]=wife[i];
91 for(node*tmp=son[i];tmp;tmp=tmp->next)
92 if(belong[wife[i]]==belong[tmp->num]&&tmp->num!=wife[i])
93 cnt_girl[j++]=tmp->num;
94 printf("%d",j);
95 sort(cnt_girl,cnt_girl+j);
96 for(int m=0;m<j;++m)
97 printf(" %d",cnt_girl[m]);
98 printf("\n");
99 }
100 ini();
101 }
102 return 0;
103 }