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;
}