poj 2762 Going from u to v or from v to u? trajan+拓扑

时间：2016-04-08 21:42:42 阅读：364 评论：0 收藏：0 [点我收藏+]

Going from u to v or from v to u?

Description

In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn‘t know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything?

Input

The first line contains a single integer T, the number of test cases. And followed T cases.

The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly.

Output

The output should contain T lines. Write ‘Yes‘ if the cave has the property stated above, or ‘No‘ otherwise.

Sample Input

Sample Output

Yes
题解：求这图是不是单联通；缩点以后这图一定是一个链；
数据
3
3 2
1 2
3 2
5 4
1 2
2 3
3 4
4 5
5 4
1 2
1 3
3 4
3 5
No
Yes
No

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define ll __int64
#define inf 2000000001
int scan()
{
    int res = 0 , ch ;
    while( !( ( ch = getchar() ) >= ‘0‘ && ch <= ‘9‘ ) )
    {
        if( ch == EOF )  return 1 << 30 ;
    }
    res = ch - ‘0‘ ;
    while( ( ch = getchar() ) >= ‘0‘ && ch <= ‘9‘ )
        res = res * 10 + ( ch - ‘0‘ ) ;
    return res ;
}
struct is
{
    int u,v;
    int next;
}edge[50010],edgetop[50010];
int head[50010];
int belong[50010];
int dfn[50010];
int low[50010];
int stackk[50010];
int instack[50010];
int du[100010];
int n,m,jiedge,lu,bel,top,jiedgetop;
void update(int u,int v)
{
    jiedge++;
    edge[jiedge].u=u;
    edge[jiedge].v=v;
    edge[jiedge].next=head[u];
    head[u]=jiedge;
}
void updatetop(int u,int v)
{
    jiedgetop++;
    edgetop[jiedgetop].u=u;
    edgetop[jiedgetop].v=v;
    edgetop[jiedgetop].next=head[u];
    head[u]=jiedgetop;
}
void dfs(int x)
{
    dfn[x]=low[x]=++lu;
    stackk[++top]=x;
    instack[x]=1;
    for(int i=head[x];i;i=edge[i].next)
    {
        if(!dfn[edge[i].v])
        {
            dfs(edge[i].v);
            low[x]=min(low[x],low[edge[i].v]);
        }
        else if(instack[edge[i].v])
        low[x]=min(low[x],dfn[edge[i].v]);
    }
    int ne;
    if(low[x]==dfn[x])
    {
        //cout<<x<<" "<<"XXX"<<endl;
        bel++;
        do
        {
            ne=stackk[top--];
            belong[ne]=bel;
            instack[ne]=0;
        }while(x!=ne);
    }
}
void tarjan()
{
    memset(dfn,0,sizeof(dfn));
    bel=lu=top=0;
    for(int i=1;i<=n;i++)
    if(!dfn[i])
    dfs(i);
}
int topsort()
{
    int st;
    int flag=0;
    for(int i=1;i<=bel;i++)
    {
        if(du[i]==0)
        {
            flag++;
            st=i;
        }
    }
    if(flag>1) return 0;
    int n=bel,en;
    while(n--)
    {
        int flagg=0;
        for(int i=head[st];i;i=edgetop[i].next)
        {
            en=edgetop[i].v;
            du[en]--;
            if(du[en]==0)
            {
                flagg++;
                st=en;
            }
        }
        if(flagg>1) return 0;
    }
    return 1;
}
int main()
{
    int i,t;
    int nn;
    scanf("%d",&nn);
    while(nn--)
    {
        scanf("%d%d",&n,&m);
        memset(head,0,sizeof(head));
        memset(belong,0,sizeof(belong));
        jiedge=0;
        for(i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            update(u,v);
        }
        tarjan();
        memset(head,0,sizeof(head));
        memset(du,0,sizeof(du));
        jiedgetop=0;
       /* cout<<bel<<endl;
        for(i=1;i<=n;i++)
        cout<<belong[i]<<endl;*/
        for(int i=1;i<=m;i++)
        {
            int u=edge[i].u;
            int v=edge[i].v;
            if(belong[u]!=belong[v])
            {
                du[belong[v]]++;
                updatetop(belong[u],belong[v]);
            }
        }
        if(topsort())
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}
/*
3 2
1 2
3 2
*/

View Code

poj 2762 Going from u to v or from v to u? trajan+拓扑

原文：http://www.cnblogs.com/jhz033/p/5369954.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)