HDU 3749 Financial Crisis(点-双连通分量)
http://acm.hdu.edu.cn/showproblem.php?pid=3749
题意:给你一个(保证输入无重边,无自环)无向图,然后有下面Q条询问,每条询问为:问你u点与v点之间有几条(除了首尾两点外,其他点不重复)的路径.如果有0条或1条输出0或1,如果有2条以上,输出”two or more”.
分析:
首先如果u点与v点不连通,直接输出0即可.(用并查集实现)
然后如果u点与v点属于同一个点-双连通分量,输出two or more.(这里有特例,两点一边的点-双连通分量应该输出1)
剩下的所有情况表示u与v虽然连通,但是在不同的点-双连通分量类,直接输出1即可.
Q:如果该题仅要求u与v的不同路径边不同即可,情况又是如何呢?(这种情况更简单,只需考虑边-双连通分量即可且没有特例)
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
const int maxn=5000+10;
int n,m,q;
vector<int> G[maxn], bcc[maxn];
int dfs_clock,bcc_cnt;
int pre[maxn],low[maxn],bccno[maxn];
vector<int> belong[maxn];//belong[i]表示第i个节点属于的所有点双连通分量编号
struct Edge
{
int u,v;
Edge(int u,int v):u(u),v(v){}
};
stack<Edge> S;
void dfs(int u,int fa)
{
low[u]=pre[u]=++dfs_clock;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(v==fa) continue;
Edge e=Edge(u,v);
if(!pre[v])
{
S.push(e);
dfs(v,u);
low[u]=min(low[v],low[u]);
if(low[v]>=pre[u])
{
bcc_cnt++; bcc[bcc_cnt].clear();
while(true)
{
Edge x=S.top(); S.pop();
if(bccno[x.u]!=bcc_cnt)
{
bcc[bcc_cnt].push_back(x.u), bccno[x.u]=bcc_cnt;
belong[x.u].push_back(bcc_cnt);
}
if(bccno[x.v]!=bcc_cnt)
{
bcc[bcc_cnt].push_back(x.v), bccno[x.v]=bcc_cnt;
belong[x.v].push_back(bcc_cnt);
}
if(x.u==u && x.v==v) break;
}
}
}
else if(pre[v]<pre[u])
{
S.push(e);
low[u]=min(low[u],pre[v]);
}
}
}
int fa[maxn];
int find(int i)
{
if(fa[i]==-1) return i;
return fa[i]=find(fa[i]);
}
int main()
{
int kase=0;
while(scanf("%d%d%d",&n,&m,&q)==3&&n)
{
bcc_cnt=dfs_clock=0;
memset(pre,0,sizeof(pre));
memset(bccno,0,sizeof(bccno));
memset(fa,-1,sizeof(fa));
for(int i=0;i<n;i++) G[i].clear(),belong[i].clear();
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
u=find(u), v=find(v);
if(u!=v) fa[u]=v;
}
for(int i=0;i<n;i++)
if(!pre[i]) dfs(i,-1);
printf("Case %d:\n",++kase);
while(q--)
{
int u,v;
scanf("%d%d",&u,&v);
if(find(u)!=find(v)) printf("zero\n");
else
{
bool flag=false;
//u点与v点所属的点双连通分量集合有交集,注意可能交集数<=1
//以上结论可以分情况证明出来,注意两个割点的分量交集数<=1
for(int i=0;i<belong[u].size()&&!flag;i++)
for(int j=0;j<belong[v].size()&&!flag;j++)
{
if(belong[u][i]==belong[v][j])
{
int num=belong[u][i];
if(bcc[num].size()>2)
printf("two or more\n"),flag=true;
}
}
if(!flag) printf("one\n");
}
}
}
return 0;
}
分享到:
相关推荐
第一章 功能简介本章介绍HDU-EID-V2开发板的功能,使大家对该开发板的功能及特点有个基本了解。1. 处理器( MCU)HDU-EID-V2 开发板的处理器
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
很适合ACM初学者的文档, 题目,代码,解体思路一应俱全
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
1、开发板外观说明 2、电源供电 3、连接调试方法 4、复用功能选择说明
求一个有向图n个点 m 条边,是否是强连通分量,如果是输出Yes, 不是输出No. 数据范围 n < 10000, m < 100000 思路: Tarjan模板题 补习: AC code: /* Tarjan求有向图的强连通分量, */ #include #...
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
教程来自HDU 的ACM教案,非常好的一个资料
教程来自HDU 的ACM教案,非常好的一个资料
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
HDU 1010-2500解题报告,ACMer可以借鉴一下
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
hdu2000-2014ac代码,虽然只有几道,但都是简单的
HDU 里面的2000~2099道题目的源码。谢谢支持
杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭州电子科技大学ACM Steps中Chapter One-Section Two的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh