POJ 1904 King's Quest

http://poj.org/problem?id=1904
方法同HDU 4685 2013多校8 1010，只是那道题需要自己找匹配，这道题已经给定了匹配了。
根据初始给定的匹配直接找强连通分量，在同一强连通分量的人可以配对。
这题试了一下std::ios_base::sync_with_stdio(false);，加了这句cin比scanf竟然还快。。。。。。
  1 //#pragma comment(linker, "/STACK:102400000,102400000")
  2 #include<cstdio>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<string>
  6 #include<cmath>
  7 #include<set>
  8 #include<list>
  9 #include<map>
 10 #include<iterator>
 11 #include<cstdlib>
 12 #include<vector>
 13 #include<queue>
 14 #include<stack>
 15 #include<algorithm>
 16 #include<functional>
 17 using namespace std;
 18 typedef long long LL;
 19 #define ROUND(x) round(x)
 20 #define FLOOR(x) floor(x)
 21 #define CEIL(x) ceil(x)
 22 const int maxn=4040;
 23 const int maxm=400010;
 24 const int inf=0x3f3f3f3f;
 25 const LL inf64=0x3f3f3f3f3f3f3f3fLL;
 26 const double INF=1e30;
 27 const double eps=1e-6;
 28 int N,g[maxn/2][maxn/2];
 29 int Mx[maxn];
 30 struct Edge
 31 {
 32     int v,next;
 33 }edge[maxm];
 34 int edgeNum,head[maxn];
 35 void addSubEdge(int u,int v)
 36 {
 37     edge[edgeNum].v=v;
 38     edge[edgeNum].next=head[u];
 39     head[u]=edgeNum++;
 40 }
 41 int sid[maxn];
 42 int mark[maxn],low[maxn];
 43 int check[maxn];
 44 int sstack[maxn],top;
 45 int dfn,ssn;
 46 int n,m;
 47 void dfs(int k)
 48 {
 49     int i,j;
 50     check[k]=1;
 51     low[k]=mark[k]=dfn++;
 52     sstack[top++]=k;
 53     for(int i=head[k]; i!=-1; i=edge[i].next)
 54     {
 55         int j=edge[i].v;
 56         if(mark[j]==0)
 57         {
 58             dfs(j);
 59             low[k]=min(low[k],low[j]);
 60         }
 61         else if(check[j])
 62             low[k]=min(low[k],mark[j]);
 63     }
 64     if(mark[k]==low[k])
 65     {
 66         while(sstack[--top]!=k)
 67         {
 68             check[sstack[top]]=0;
 69             sid[sstack[top]]=ssn;
 70         }
 71         sid[k]=ssn;
 72         check[k]=0;
 73         ++ssn;
 74     }
 75     return;
 76 }
 77 void tarjan()
 78 {
 79     ssn=1;
 80     dfn=1;
 81     top=0;
 82     memset(check,0,sizeof(check));
 83     memset(mark,0,sizeof(mark));
 84     for(int i=0; i<n; ++i) if(mark[i]==0) dfs(i);
 85 }
 86 void init()
 87 {
 88     memset(g,0,sizeof(g));
 89     memset(head,-1,sizeof(head));
 90     edgeNum=0;
 91 }
 92 void input()
 93 {
 94     for(int i=0; i<N; i++)
 95     {
 96         int k;
 97 //        scanf("%d",&k);
 98         cin>>k;
 99         while(k--)
100         {
101             int x;
102             cin>>x;
103 //            scanf("%d",&x);
104             g[i][x-1]=1;
105             addSubEdge(i,x+N-1);
106         }
107     }
108     for(int i=0;i<N;i++)
109     {
110         int x;
111         cin>>x;
112 //        scanf("%d",&x);
113         addSubEdge(x+N-1,i);
114     }
115 }
116 void solve()
117 {
118     n=N;
119     tarjan();
120 }
121 void output()
122 {
123     vector<int> ans;
124     for(int i=0;i<N;i++)
125     {
126         ans.clear();
127         for(int j=N;j<2*N;j++)
128         {
129             if(g[i][j-N]&&sid[i]==sid[j])
130             {
131                 ans.push_back(j-N+1);
132             }
133         }
134         cout<<ans.size();
135 //        printf("%d",ans.size());
136         for(int j=0;j<ans.size();j++)
137         {
138             cout<<" "<<ans[j];
139 //            printf(" %d",ans[j]);
140         }
141         cout<<endl;
142 //        puts("");
143     }
144 }
145 int main()
146 {
147     std::ios_base::sync_with_stdio(false);
148 //    freopen("in.cpp","r",stdin);
149     while(cin>>N)
150     {
151         init();
152         input();
153         solve();
154         output();
155     }
156     return 0;
157 }
View Code