POJ 1904 King's Quest 强联通分量+输入输出外挂

题意：国王有n个儿子，现在这n个儿子要在n个女孩里选择自己喜欢的，有的儿子可能喜欢多个，最后国王的向导给出他一个匹配。匹配有n个数，代表某个儿子和哪个女孩可以结婚。已知这些条件，要你找出每个儿子可以和哪些女孩结婚

思路：求强联通分量。同时练习一下输入输出外挂可以减少时间

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<cstdlib>

 #include<string>

 #include<cmath>

 #include<vector>

 using namespace std;

 const int maxn=1e5+;

 const double eps=1e-;

 const double pi=acos(-);

 const int inf = 0x3f3f3f3f;

 #define ll long long

 #define clc(a,b) memset(a,b,sizeof(a))

 const int N=;

 const int M=;

 struct Edge {

     int v,next;

 } edge[M];

 int first[N],low[N],dfn[N],sta[M],belong[N],ans[N];

 bool instack[N];

 int g,cnt,top,scc;

 void addedge(int u,int v) {

     edge[g].v=v;

     edge[g].next=first[u];

     first[u]=g++;

 }

 int min(int a,int b) {

     return a<b?a:b;

 }

 void tarjan(int u) {

     int i,v;

     low[u]=dfn[u]=++cnt;

     sta[++top]=u;

     instack[u]=true;

     for(i=first[u]; i!=-; i=edge[i].next) {

         v=edge[i].v;

         if(!dfn[v]) {

             tarjan(v);

             low[u]=min(low[u],low[v]);

         } else if(instack[v]) {

             low[u]=min(low[u],dfn[v]);

         }

     }

     if(low[u]==dfn[u]) {

         scc++;

         while() {

             v=sta[top--];

             instack[v]=false;

             belong[v]=scc;

             if(u==v)

                 break;

         }

     }

 }

 int scan() {

     int res=,ch,flag=;

     if((ch=getchar())=='-')

         flag=;

     else if(ch>=''&&ch<='')

         res=ch-'';

     while((ch=getchar())>=''&&ch<='')

         res=res*+ch-'';

     return flag?-res:res;

 }

 void out(int a) {

     if(a>)

         out(a/);

     putchar(a%+'');

 }

 int main() {

     int n,i,u,v,k;

     while(scanf("%d",&n)!=EOF) {

         g=cnt=top=scc=;

         clc(first,-);

         clc(dfn,);

         clc(instack,false);

         for(i=; i<=n; i++) {

             k=scan();

             while(k--) {

                 v=scan();

                 addedge(i,v+n);

             }

         }

         for(i=;i<=n;i++){

             v=scan();

             addedge(v+n,i);

         }

          for(i=;i<=*n;i++){

             if(!dfn[i])

                 tarjan(i);

          }

          for(u=;u<=n;u++){

             int countt=;

             for(i=first[u];i!=-;i=edge[i].next){

                 v=edge[i].v;

                 if(belong[u]==belong[v])

                     ans[countt++]=v-n;

             }

             sort(ans,ans+countt);

             out(countt);

             for(i=;i<countt;i++){

                 putchar(' ');

                 out(ans[i]);

             }

             putchar('\n');

          }

     }

     return ;

 }