poj 2762 Going from u to v or from v to u?

时间：2023-03-09 19:18:54
poj 2762 Going from u to v or from v to u? 
题目描述：
为了让他们的儿子变得更勇敢些，Jiajia和Wind将他们带到一个大洞穴中。洞穴中有n个房
间，有一些单向的通道连接某些房间。每次，Wind选择两个房间x和y，要求他们的一个儿子从
一个房间走到另一个房间，这个儿子可以从x走到y，也可以从y走到x。Wind保证她布置的任
务是可以完成的，但她确实不知道如何判断一个任务是否可以完成。为了使Wind下达任务更容
易些，Jiajia决定找这样的一个洞穴，每对房间（设为x和y）都是相通（可以从x走到y，或者
可以从y走到x）的。给定一个洞穴，你能告诉Jiajia，Wind是否可以任意选择两个房间而不用
担心这两个房间可能不相通吗？
// 
求解的是单连通性，但首先要转换成强连通分量的求解。这是因为，强连通分量中
的顶点间存在双向的路径，因此可以将每个强连通分量收缩成一个新的顶点。在有向图的处理中
经常需要将强连通分量收缩成一个顶点。

强连通分量收缩后，再求其拓扑排序。假设求得的拓扑序存储在topo[MAX]中，topo[i]与
topo[i+1]存在边连通（i 到i+1 或i+1 到i），则定有i 到i+1 的边。而如果每个topo[i]与topo[i+1]
都存在边连通（即有i 到i+1 的边）时，topo[i]到任意topo[j]便都有边连通。
// topsort时偷懒 用了邻接矩阵 复杂度成了 n^2  写成邻接表应该要快好多
#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#include <math.h>

#include <stdio.h>

#include <string.h>

using namespace std;

#define MOD 1000000007

#define maxn 6100

#define maxm 1010

struct Edge{

    int to;

    int next;

    Edge(){};

    Edge(int u,int v){to=u;next=v;}

}E[maxn];

stack<int> S;

int V[maxm],num;

int belong[maxm];

int pre[maxm];

int dfst,scc;

int ans;

bool G[maxm][maxm];

int in[maxm];

void init(int n){

    dfst=scc=;

    num=;

    ans=;

    while(!S.empty())

        S.pop();

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

        V[i]=-;

        pre[i]=;

        belong[i]=;

    }

}

void add(int u,int v){

    E[num].to=v;

    E[num].next=V[u];

    V[u]=num++;

}

int tarjan(int u){

   int lowu=pre[u]=++dfst;

   int v,e;

   S.push(u);

   for(e=V[u];e!=-;e=E[e].next){

        v=E[e].to;

          if(!pre[v]){

            int lowv=tarjan(v);

            lowu=min(lowu,lowv);

          }

          else if(!belong[v]) lowu=min(lowu,pre[v]);

   }

    if(lowu==pre[u]){

        scc++;

        for(;;){

            int x=S.top();S.pop();

            belong[x]=scc;

            if(x==u) break;

        }

    }

   return lowu;

}

int top[maxm],tn;

void topsort(){

   int i,j,k;

   tn=;

   bool vi[maxm]={};

   while(){

    for(i=;i<=scc;i++)

      if(!in[i]&&!vi[i]) break;

      vi[i]=true;

    //  printf("%d ",i);

    if(i>scc) break;

     top[tn++]=i;

    for(j=;j<=scc;j++)

        if(G[i][j]) in[j]--;

   }

}

int main()

{

    int n,m,T;

    int u,v;

    int i,j=;

    scanf("%d",&T);

    while(T--){

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

        init(n);

        for(i=;i<=m;i++){

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

            add(u,v);

        }

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

          if(!pre[i]) tarjan(i);

     // for(i=1;i<=n;i++) printf("%d ",belong[i]);

       for(i=;i<=scc;in[i]=,i++)

        for(j=;j<=scc;j++)

           G[i][j]=;

        int e,u,v;

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

        {

           for(e=V[i];e!=-;e=E[e].next){

              u=belong[i];

              v=belong[E[e].to];

              if(u!=v){

                    G[u][v]=;

                    in[v]++;

                  //  printf("%d ",v);

              }

           }

        }

        topsort();//printf("\\");

        int flag=;

        for(i=;i<tn;i++)

         if(!G[top[i-]][top[i]]){

            flag=;break;

        }

        if(flag) printf("Yes\n"); else printf("No\n");

    }

    return ;

}

相关文章