大致题意:
有n个帅哥要泡n个美女。对于每个帅哥,给出他可以选择的美女序号。然后给出一个可行的匹配。对于每个帅哥,求出他可以选择哪些美女,才能使得所有帅哥都有马子泡。
大致思路:
很神奇的一道强连通题目,点数达到8000,边数达到20000000,肯定不能够直接爆搜。更诡异的是他给出了一组可行的匹配,这和题目有关系么?其实,这个才是解题的关键!把所有的帅哥和美女都抽象成有向图的节点,如果一个帅哥i可以选择美女j,则连接i->j。如果在给出的可行匹配中如果帅哥i匹配美女j,则连边j->i。
对这个图求出强联通分量,可以看出在一个强连通分量中帅哥的个数等于美女。对于帅哥i,i所在的强连通分量中所有的他喜欢的美女他都可以选择,而不用顾忌影响其他帅哥。所以输出他所在的强连通分量中他喜欢的美女编号即可。
另外不知道为什么最后判断男女是否处于同一分量时必须使用原始的邻接表, 而不能直接在下标[n, 2n)中判断~~囧
#include<iostream>
#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax=30015;
const int mMax=500100;
class edge{
public:
int v,nex;
};edge e[mMax];
int k,head[nMax];//head[i]是以点i为起点的链表头部
void addedge(int a,int b){//向图中加边的算法,注意加上的是有向边//b为a的后续节点既是a---->b
e[k].v=b;
e[k].nex=head[a];
head[a]=k;k++;
}
int dfn[nMax],low[nMax],sta[nMax],top,atype,belon[nMax],dep; //atype 强连通分量的个数
bool insta[nMax];
void Tarjan(int u){ //我的Tarjan模版
int i,j;
dfn[u]=low[u]=++dep;
sta[++top]=u;
insta[u]=1;
for(i=head[u];i;i=e[i].nex){
int v=e[i].v;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else{
if(insta[v])low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
atype++; //强连通分量个数
do{
j=sta[top--];
belon[j]=atype; //第j个点属于第type个连通块
insta[j]=0;
}while(u!=j);
}
}
void init(){
k=1;
dep=1;
top=atype=0;
memset(insta,0,sizeof(insta)); //是否在栈中
memset(head,0,sizeof(head)); //静态链表头指针
memset(low,0,sizeof(low)); //Tarjan的low数组
memset(dfn,0,sizeof(dfn)); //Tarjan的dfn数组
memset(belon,0,sizeof(belon)); //记录每个点属于哪一个强连通分量
}
int ans[nMax];
int main(){
int n,a,m,i,j,b;
while(scanf("%d",&n)!=EOF){
init();
for(i=1;i<=n;i++){
scanf("%d",&m);
while(m--){
scanf("%d",&a);
addedge(i,n+a);
}
}
for(i=1;i<=n;i++){
scanf("%d",&a);
addedge(n+a,i);
}
for(i=1;i<=2*n;i++){
if(!dfn[i]){
Tarjan(i);
}
}
for(i=1;i<=n;i++){
b=0;
for(j=head[i];j;j=e[j].nex){
int v=e[j].v;
if(belon[i]==belon[v]){
ans[b++]=v-n;
}
}
sort(ans,ans+b);
printf("%d ",b);
for(j=0;j<b;j++){
printf("%d ",ans[j]);
}
printf("\n");
}
}
return 0;
}
分享到:
相关推荐
)图作为输入,并以拓扑顺序返回其强连通分量作为输出 循环依赖 在各种情况下,依赖关系可能是循环的,并且必须同时执行一组相互依赖的操作。同时执行成本高昂的情况并不少见。使用 Tarjan 算法,可以确定执行相互...
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
求有向图的强连通分量(scc)Tarjan算法.docx
使用Tarjan算法进行快速计算强连通分量,C++语言实现。
Tarjan求有向图的强连通分量, */ #include #include #include #include #include using namespace std; const int MAXN = 1e5 + 10; struct Edge{ int to, next, dis; }edge[MAXN << 1];
图论- 图的连通性- Tarjan 求强连通分量.rar
详细地介绍了如何计算强连通分量,图文并茂地阐述了tarjan算法的流程和原理,两者均有模板。
而有向图G的极大强连通子图S,即添加任意顶点都会导致S失去强连通的属性,则称S为G的强连通分量。 其中有经典的塔尖(Tarjan)算法: 思路不难理解,因为任何一个强连通分量,必定是对原图的深度优先搜索树的子树...
实现用于查找有向图的强连通分量的 Tarjan 算法。 在强连通分量 (SCC) 中,每个节点到每个其他节点都有一条路径。 SCC 是不相交的。 入度或出度为零或属于无环图的节点自己形成 SCC。 接受邻接矩阵作为输入。 为了...
纯代码
在有向图中,如果从节点A到节点B存在一条有向路径,并且从节点B到节点A也存在一条有向路径,则节点A和节点B属于同一个强连通分量。 以下是使用C语言实现查找强连通分量的示例代码,基于深度优先搜索(DFS)算法和...
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
Tarjan算法是用来求有向图的强连通分量的。求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法,以及求最近公共祖先的离线Tarjan算法 (本篇文章...
POJ2942-Knights of the Round Table 【Tarjan算法】 解题报告+AC代码 http://hi.csdn.net/!s/F3L8HO ================================== 我的POJ所有解题报告:...
图论- 图的连通性- Tarjan 求双连通分量.rar
C++实现Tarjan算法的一个简单模板,求有向图的强连通分量。时间复杂度为O(N+M)。
Tarjan割点割边,强联通分量讲解
C语言中的强连接组件Tarjan算法的实现,用于在有向图中找到强连接的组件。 图在graph.gx文件中表示。 节点数,每个节点的名称和每个节点的边缘应在不同的行中声明。 请以graph.gx为例。 我使用了伯克利大学开发的...