首页 > 代码库 > [POJ 2762]Going from u to v or from v to u? (强连通分量+拓扑排序)

[POJ 2762]Going from u to v or from v to u? (强连通分量+拓扑排序)

2024-07-17 16:41:45   222人阅读

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

1
3 3
1 2
2 3
3 1

Sample Output

Yes

Source

POJ Monthly--2006.02.26,zgl & twb

题目大意：给定一个有向图，判断图中任意两点u,v是否能从u到达v或从v到达u，可以的话输出Yes，不行输出No

注意这里是或者不是而且，如果是而且的话直接判断整个图是不是一个强连通分量即可，简单很多，此题的思路是先将整图缩点(每个强连通分量中任意两点均可达)，对缩点后的DAG进行拓扑排序，在排序过程中若出现多个入点为0的点则判定排序失败，若最终拓扑排序成功则表明图中任意两点u,v能从u到达v或从v到达u

#include <iostream>
#include <string.h>

#define MAXV 8010
#define MAXE 2010
#define cls(array,num) memset(array,num,sizeof(array))

using namespace std;

struct edge
{
    int u,v,next;
}edges[MAXV],newedges[MAXV];

int head[MAXE],dfn[MAXE],low[MAXE],belong[MAXE],stack[4*MAXE],inDegree[MAXE];
bool inStack[MAXE];
int top=0,nCount=0,newCount=0,tot=0,index=0,n,m;

int min(int a,int b)
{
    if(a<b) return a;
    return b;
}

void AddEdge(int U,int V,edge arr[],int& count)
{
    arr[++count].u=U;
    arr[count].v=V;
    arr[count].next=head[U];
    head[U]=count;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++index;
    stack[++top]=u;
    inStack[u]=true;
    for(int p=head[u];p!=-1;p=edges[p].next)
    {
        int v=edges[p].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(inStack[v])
            low[u]=min(low[u],dfn[v]);
    }
    int v;
    if(dfn[u]==low[u])
    {
        tot++;
        do
        {
            v=stack[top--];
            belong[v]=tot;
            inStack[v]=false;
        }while(u!=v);
    }
}

void newGraph() //缩点建图,新图在newedges里
{
    cls(head,-1);
    for(int i=1;i<=nCount;i++)
    {
        int u=edges[i].u,v=edges[i].v;
        if(belong[u]!=belong[v])
        {
            AddEdge(belong[u],belong[v],newedges,newCount);
            inDegree[belong[v]]++;
        }
    }
}

bool topologicalSort()
{
    int ans=0,num;
    for(int i=1;i<=tot;i++)
    {
        if(inDegree[i]==0)
        {
            ans++;
            num=i;
        }
    }
    if(ans>1) return false;
    int rest=tot,result[MAXE];
    while(rest--)
    {
        ans=0;
        for(int p=head[num];p!=-1;p=newedges[p].next)
        {
            int v=newedges[p].v;
            inDegree[v]--;
            if(inDegree[v]==0)
            {
                ans++;
                num=v;
            }
        }
        if(ans>1) return false;
    }
    return true;
}

int main()
{
    int testCase;
    cin>>testCase;
    while(testCase--)
    {
        cls(head,-1);
        cls(dfn,0);
        cls(low,0);
        cls(stack,0);
        cls(inStack,0);
        cls(belong,0);
        cls(inDegree,0);
        top=0,nCount=0,newCount=0,tot=0,index=0;
        for(int i=0;i<MAXV;i++)
        {
            edges[i].u=0;
            edges[i].v=0;
            edges[i].next=0;
            newedges[i].u=0;
            newedges[i].v=0;
            newedges[i].next=0;
        }
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            int a,b;
            cin>>a>>b;
            AddEdge(a,b,edges,nCount);
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i]) tarjan(i);
        newGraph();
        if(topologicalSort())
            cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}




联系
我们