【CSP模拟赛】Freda的迷宫（桥）

题目描述

Freda是一个迷宫爱好者，她利用业余时间建造了许多迷宫。每个迷宫都是由若干房间和走廊构成的，每条走廊都连接着两个不同的房间，两个房间之间最多只有一条走廊直接相连，走廊都是双向通过。
黄昏时候，Freda喜欢在迷宫当中漫步。每天，Resodo都会为Freda设计一个挑战方案。Resodo会指定起点和终点，请Freda来找到一条从起点到终点的简单路径。一条简单路径定义为一个房间序列，每个房间至多在序列里出现一次，且序列中相邻的两个房间有走廊相连。当起点和终点之间存在且仅存在一条简单路径的时候，Freda认为这个挑战方案是RD的。现在，请你帮帮Resodo来写一个程序，判断一个挑战方案是否是RD的。

输入格式

第一行三个整数N,M,Q.分别表示房间数，走廊数，询问数。
接下来M行每行2个整数x,y, 0<x,y<=N, 表示x和y之间有一条走廊相连。
接下来Q行每行2个整数x,y, 表示询问以x为起点,y为终点的挑战方案是否是RD的.

输出格式

对于每个询问，输出一行”Y”或者”N”（不含引号）.Y表示该询问所表示的挑战方案是RD的,N表示该询问所表示的挑战方案不是RD的.
输入样例
6 5 3
1 2
2 3
2 4
2 5
4 5
1 3
1 5
2 6
输出样例
Y
N
N
提示
样例解释
1,3之间只有一条路径 1->2->3
1,5之间有两条路径 1->2->5 ; 1->2->4->5
1,6之间没有路径
数据范围与约定
对于30%的数据，N<=100， M<=1000, Q<=100.
对于50%的数据，N<=1000, M<=10000, Q<=1000.
对于100%的数据，N<=10000, M<=100000, Q<=10000.

分析

最近智商真的是越来越低了，一个题想了半天（感觉CSP药丸？

两个点之间只存在一条简单路径，那么这条路径上所有的边一定都是原图中的桥（割边），不然这些边之间就存在环，这些边就可以由其它边代替

于是就想了半天如何判断路径中只含割边

其实只需要将所有割边求出来然后只连割边，在同一个连通块里的点之间的路径就是只含割边的

Code

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

const int maxm=;

int n,m,id,cnt,ecnt,Q,info[maxn],nx[maxm<<],v[maxm<<];

int dfn[maxn],low[maxn],ori[maxn],scc[maxn];

int find(int x){return !ori[x]?x:ori[x]=find(ori[x]);}

void add(int u1,int v1){nx[++ecnt]=info[u1];info[u1]=ecnt;v[ecnt]=v1;}

void dfs(int x,int f)

{

    low[x]=dfn[x]=++id;

    for(int e=info[x];e;e=nx[e])

    if(!dfn[v[e]])

    {

        dfs(v[e],x),low[x]=min(low[x],low[v[e]]);

        if(low[v[e]]>dfn[x])

        {

            int s1=find(v[e]),s2=find(x);

            if(s1!=s2)ori[s1]=s2;

        }

    }

    else if(v[e]!=f)low[x]=min(low[x],dfn[v[e]]);

}

int main()

{

    scanf("%d%d%d",&n,&m,&Q);

    for(int i=,u1,v1;i<=m;i++)scanf("%d%d",&u1,&v1),add(u1,v1),add(v1,u1);

    for(int i=;i<=n;i++)if(!dfn[i])dfs(i,);

    for(int i=,x,y;i<=Q;i++)

    {

        scanf("%d%d",&x,&y);

        if(find(x)==find(y))puts("Y");

        else puts("N");

    }

freda