COGS 1043. [Clover S2] Freda的迷宫

★ 输入文件：mazea.in 输出文件：mazea.out 简单对比
时间限制：1 s 内存限制：128 MB Freda 的迷宫

(mazea.pas/.c/.cpp)

题目叙述

Freda 是一个迷宫爱好者，她利用业余时间建造了许多迷宫。每个迷宫都是由若干房间

和走廊构成的，每条走廊都连接着两个不同的房间，两个房间之间最多只有一条走廊直接相

连，走廊都是双向通过。

黄昏时候，Freda 喜欢在迷宫当中漫步。每天，Resodo 都会为Freda 设计一个挑战方案。

Resodo 会指定起点和终点，请Freda 来找到一条从起点到终点的简单路径。一条简单路径定

义为一个房间序列，每个房间至多在序列里出现一次，且序列中相邻的两个房间有走廊相连。

当起点和终点之间存在且仅存在一条简单路径的时候，Freda 认为这个挑战方案是RD 的。现

在，请你帮帮Resodo 来写一个程序，判断一个挑战方案是否是RD 的。

输入格式

第一行三个整数N,M,Q.分别表示房间数，走廊数，询问数。

接下来M 行每行2 个整数x,y, 0<x,y<=n, 表示x="" 和y="" 之间有一条走廊相连。<="" span="">

接下来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

输出样例

样例解释

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.

tarjan求桥

Rank1( 偷笑 )

屠龙宝刀点击就送

#include <cstdio>

#define N 200005

int n,m,q,cnt,tim,fa[N],to[N<<],dfn[N],low[N],head[N],nextt[N<<];

void ins(int u,int v)

{

    nextt[++cnt]=head[u];to[cnt]=v;head[u]=cnt;

    nextt[++cnt]=head[v];to[cnt]=u;head[v]=cnt;

}

int find_(int x) {return x==fa[x]?x:fa[x]=find_(fa[x]);}

inline int min(int a,int b) {return a>b?b:a;}

void tarjan(int x,int pre)

{

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

    for(int i=head[x];i;i=nextt[i])

    {

        int v=to[i];

        if(v==pre) continue;

        if(!dfn[v])

        {

            tarjan(v,x);

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

            if(low[v]>dfn[x]) fa[find_(v)]=find_(x);

        }

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

    }

}

int Main()

{

    freopen("mazea.in","r",stdin);

    freopen("mazea.out","w",stdout);

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

    for(int u,v;m--;)

    {

        scanf("%d%d",&u,&v);

        ins(u,v);

    }

    for(int i=;i<=n;++i) fa[i]=i;

    for(int i=;i<=n;++i)

     if(!dfn[i]) tarjan(i,);

    for(int x,y;q--;)

    {

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

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

        else puts("N");

    }

    return ;

}

int sb=Main();

int main(int argc,char *argv[]) {;}

巴特西

COGS 1043. [Clover S2] Freda的迷宫

最新文章

热门文章