1076 2条不相交的路径
基准时间限制:1 秒 空间限制:131072 KB 分值: 40
难度:4级算法题
(注,无向图中不存在重边,也就是说确定起点和终点,他们之间最多只有1条路)
Input
第1行:2个数M N,中间用空格分开,M是顶点的数量,N是边的数量。(2 <= M <= 25000, 1 <= N <= 50000)
第2 - N + 1行,每行2个数,中间用空格分隔,分别是N条边的起点和终点的编号。例如2 4表示起点为2,终点为4,由于是无向图,所以从4到2也是可行的路径。
第N + 2行,一个数Q,表示后面将进行Q次查询。(1 <= Q <= 50000)
第N + 3 - N + 2 + Q行,每行2个数s, t,中间用空格分隔,表示查询的起点和终点。
Output
共Q行,如果从s到t存在2条不相交的路径则输出Yes,否则输出No。
Input示例
4 4
1 2
2 3
1 3
1 4
5
1 2
2 3
3 1
2 4
1 4
Output示例
Yes
Yes
Yes
No
No
边双连通分量的求法:
先dfs一次求出所有的桥-.-将桥标记----然后再dfs一次,既可找到所以得分量-.-
定义 先深标记pre数组 所达到的最小pre的------low数组
low[v] 为 <1> v的所有孩子 i 的low[i] < 2 > pre[v] < 3 > 所有的 与v相连的已遍历的 w 的 pre[w] ,其中w不为v的父节点 三者的最小值...........
如果在边 u-v 中 low[u] > low[v] 的 v为割点,u-v为桥..
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
int to;
bool biao;
}op;
vector<node> V[25100];
int n,m,dfs_clock;
int low[25100],pre[25100];//pre 先深-----后面用于记录所在分量 low所到pre最小处
void dfs(int u,int fa)
{
low[u]=pre[u]=++dfs_clock;
for (int i=0;i<V[u].size();i++)
{
int v=V[u][i].to;
if (!pre[v])
{
dfs(v,u);
low[u]=min(low[v],low[u]);
if (pre[u]<low[v])//v为割点----u-v为桥
{
V[u][i].biao=true;
}
}
else if (fa!=v)
{
low[u]=min(low[u],pre[v]);
}
}
}
void dfs_shu(int u,int fa,int shu)
{
pre[u]=shu;
for (int i=0;i<V[u].size();i++)
{
int v=V[u][i].to;
if (V[u][i].biao||pre[v]) continue;
dfs_shu(v,u,shu);
}
}
int main()
{
scanf("%d%d",&n,&m);
int a,b,q;
while (m--)
{
scanf("%d%d",&a,&b);
op.biao=false;op.to=b;
V[a].push_back(op);op.to=a;
V[b].push_back(op);
}
dfs_clock=0;
memset(pre,0,sizeof(pre));
for (int i=1;i<=n;i++)
{
if (!pre[i]) dfs(i,-1);
}
memset(pre,0,sizeof(pre));
for (int i=1;i<=n;i++)
{
if (!pre[i]) dfs_shu(i,-1,i);
}
scanf("%d",&q);
while (q--)
{
scanf("%d%d",&a,&b);
if (pre[a]==pre[b])
printf("Yes\n");
else
printf("No\n");
}
return 0;
}