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 ;
}
上一篇:Spring的起源和背景


下一篇:odoo 人力资源工资计算拓展