首页 > 代码库 > [ tarjan + dfs ] poj 2762 Going from u to v or from v to u?

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

2024-07-25 06:00:45   222人阅读

题目链接：

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

POJ Monthly--2006.02.26,zgl & twb

[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;
}


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


联系
我们