题解：P10944 Going from u to v or from v to u?

· · 题解

题意：

给定一个图，若这个图中的任意两点 x,y，存在有从 x 通向 y 的路径或从 y 通向 x 的路径，则就输出 Yes 否则输出 No。

思路 1：

这应该是一种暴力做法。

首先根据题意，一个强连通图肯定合法，因此直接处理出强连通后，构造一个 DAG 就行了，随后再对于这个 DAG 上的每一个节点为起点 BFS 一遍这个 DAG，则所经过的每一个点都与我们的起点所连通。

定义 vis_{i,j} 表示点 i 和点 j 是否联通：如果 vis_{i,j} = 1，则点 i 和点 j 联通；如果 vis_{i,j} = 0，则点 i 和点 j 不联通。

因此到最后我们只需要枚举 i 和 j，如果出现 vis_{i,j} = 0 并且 vis_{j,i} = 0 的情况就输出 No，否则输出 Yes。

代码 1：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+1;
int T,n,m,ls,z[N];bool vis[N][N];
int top,stak[N],dfn[N],low[N],col[N],tot,Time;
queue<int>q;
struct bian{
    int qi,zhong,zhi;
}s[N*6];
void clean()
{
    tot=ls=Time=0;
    memset(z,0,sizeof(z));
    memset(vis,0,sizeof(vis));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(col,0,sizeof(col));
}
void Tarjan(int x)
{
    dfn[x]=low[x]=++Time;
    stak[++top]=x;
    for(int i=z[x];i;i=s[i].zhi)
    {
        int u=s[i].zhong;
        if(!dfn[u])
        {
            Tarjan(u);
            low[x]=min(low[x],low[u]);
        }
        else if(!col[u]) low[x]=min(low[x],low[u]);
    }
    if(dfn[x]==low[x])
    {
        col[x]=++tot;
        while(stak[top]!=x) col[stak[top--]]=tot;
        top--;
    }
}
void bfs(int x)
{
    q.push(x);
    vis[x][x]=1;
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=z[u];i;i=s[i].zhi)
        {
            int v=s[i].zhong;
            vis[x][v]=1;
            q.push(v);
        }
    }
}
void check()
{
    for(int i=1;i<=tot;i++)
      for(int j=1;j<=tot;j++)
        if(!vis[i][j]&&!vis[j][i]) {printf("No\n");return;}
    printf("Yes\n");
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        clean();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            s[++ls]=(bian){u,v,z[u]},z[u]=ls;
        }
        for(int i=1;i<=n;i++)
          if(!dfn[i]) Tarjan(i);
        int l=ls;
        ls=0;
        memset(z,0,sizeof(z));
        for(int i=1;i<=l;i++)
        {
            int x=col[s[i].qi],y=col[s[i].zhong];
            if(x!=y) s[++ls]=(bian){x,y,z[x]},z[x]=ls;
        }
        for(int i=1;i<=tot;i++)
            bfs(i);
        check();
    }
    return 0;
}

思路 2：

建出 DAG 之后，我们只要考虑这个 DAG 中的最长链的长度是否等于强连通的个数。

因为如果这个 DAG 中的最长链的长度不等于强连通的个数，则就一定存在两个强连通之间不能由其中一个到达另外一个，便不符合题意。

最长链的长度可以用拓扑 DP 求出来，设定 dp_{i} 表示以第 i 个强连通为终点的最长链的长度，则动态转移方程是：dp_{i}= \max (dp_{j}) + 1，其中的 j 表示第 i 个强连通的前驱。

代码 2：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+1;
int T,n,m,ls,z[N];
int top,stak[N],dfn[N],low[N],col[N],tot,Time,ru[N],dp[N];
queue<int>q;
struct bian{
    int qi,zhong,zhi;
}s[N*6];
void clean()
{
    tot=ls=Time=0;
    memset(z,0,sizeof(z));
    memset(dp,0,sizeof(dp));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(col,0,sizeof(col));
    memset(ru,0,sizeof(ru));
}
void Tarjan(int x)
{
    dfn[x]=low[x]=++Time;
    stak[++top]=x;
    for(int i=z[x];i;i=s[i].zhi)
    {
        int u=s[i].zhong;
        if(!dfn[u])
        {
            Tarjan(u);
            low[x]=min(low[x],low[u]);
        }
        else if(!col[u]) low[x]=min(low[x],low[u]);
    }
    if(dfn[x]==low[x])
    {
        col[x]=++tot;
        while(stak[top]!=x) col[stak[top--]]=tot;
        top--;
    }
}
void bfs()
{
    int maxi=1;
    for(int i=1;i<=tot;i++) if(!ru[i]) q.push(i),dp[i]=1;
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=z[u];i;i=s[i].zhi)
        {
            int v=s[i].zhong;
            dp[v]=max(dp[v],dp[u]+1);
            maxi=max(maxi,dp[v]);
            if(!(--ru[v])) q.push(v);
        }
    }
    if(maxi==tot) printf("Yes\n");
      else printf("No\n");
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        clean();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            s[++ls]=(bian){u,v,z[u]},z[u]=ls;
        }
        for(int i=1;i<=n;i++)
          if(!dfn[i]) Tarjan(i);
        int l=ls;
        ls=0;
        memset(z,0,sizeof(z));
        for(int i=1;i<=l;i++)
        {
            int x=col[s[i].qi],y=col[s[i].zhong];
            if(x!=y) s[++ls]=(bian){x,y,z[x]},z[x]=ls,ru[y]++;
        }
        bfs();
    }
    return 0;
}