[ tarjan + dfs ] poj 2762 Going from u to v or from v to u?

时间：2023-03-10 00:14:03
[ tarjan + dfs ] poj 2762 Going from u to v or from v to u?

题目链接：

http://poj.org/problem?id=2762

Going from u to v or from v to u?
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 14546   Accepted: 3837

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

[

problem_id=2762" style="text-decoration:none">Submit

]   [Go Back]   [Status]  
[Discuss]

题目意思：

给一幅图。推断随意两点v,u是否可到达.(u->v或v->u)都能够。

解题思路：

tarjan+dfs

先求有向图强连通分量。然后缩点建图，统计入度为0的联通分量个数。超过1肯定不行。

然后对搜索子树dfs，假设某一节点有超过一个儿子。则这两个儿子之间不能到达，不行。

代码：

//#include<CSpreadSheet.h>

#include<iostream>

#include<cmath>

#include<cstdio>

#include<sstream>

#include<cstdlib>

#include<string>

#include<string.h>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#include<ctime>

#include<bitset>

#include<cmath>

#define eps 1e-6

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define ll __int64

#define LL long long

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

#define M 1000000007

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

#define Maxn 1100

int low[Maxn],dfn[Maxn],sc,bc,sta[Maxn];

int n,m,dep,dei[Maxn],in[Maxn];

bool iss[Maxn];

vector<vector<int> >myv;

vector<vector<int> >tree;

bool hae[Maxn][Maxn];

int ans;

void tarjan(int cur)

{

    int ne;

    low[cur]=dfn[cur]=++dep;

    sta[++sc]=cur;

    iss[cur]=true;

    for(int i=0;i<myv[cur].size();i++)

    {

        ne=myv[cur][i];

        if(!dfn[ne])

        {

            tarjan(ne);

            if(low[ne]<low[cur])

                low[cur]=low[ne];

        }

        else if(iss[ne]&&dfn[ne]<low[cur])

            low[cur]=dfn[ne];

    }

    if(low[cur]==dfn[cur])

    {

        ++bc;

        do

        {

            ne=sta[sc--];

            iss[ne]=false;

            in[ne]=bc;

        }while(ne!=cur);

    }

}

void solve()

{

    dep=sc=bc=0;

    memset(iss,false,sizeof(iss));

    memset(dfn,0,sizeof(dfn));

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

        if(!dfn[i])

            tarjan(i);

}

void dfs(int cur)

{

    if(ans>2)

        return ;

    int res=0;

    for(int i=0;i<tree[cur].size();i++)

    {

        int ne=tree[cur][i];

        res++;

        dfs(ne);

    }

    if(res>=2)

        ans=INF;

}

int main()

{

    //freopen("in.txt","r",stdin);

   //freopen("out.txt","w",stdout);

   int t;

   scanf("%d",&t);

   while(t--)

   {

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

       myv.clear();

       myv.resize(n+1);

       memset(dei,0,sizeof(dei));

       for(int i=1;i<=m;i++)

       {

           int a,b;

           scanf("%d%d",&a,&b);

           myv[a].push_back(b);

       }

       solve();

       tree.clear();

       tree.resize(bc+1);

       memset(hae,false,sizeof(hae));

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

       {

           for(int j=0;j<myv[i].size();j++)

           {

               int ne=myv[i][j];

               if(in[i]!=in[ne])

               {

                   dei[in[ne]]++;

                   if(!hae[in[i]][in[ne]])

                   {

                       hae[in[i]][in[ne]]=true;

                       tree[in[i]].push_back(in[ne]);

                   }

               }

           }

       }

       ans=0;

       for(int i=1;i<=bc;i++)

            if(!dei[i])

            {

                ans++;

                dfs(i);

                if(ans>1)

                    break;

            }

       if(ans==1)

            printf("Yes\n");

       else

            printf("No\n");

   }

    return 0;

}

相关文章