题目大意

给一个有n个点m条边的有向图，对于图中任意两个点u，v，如果从u能到v，或者从v能到u，则这对顶点是可行的

如果图中任意一对顶点都是可行的，可以输出Yes，否则输出No

数据范围

$0< n< 1001,m< 6000$

题解

在这个有向图中，强连通分量一定满足条件，所以我们首先要强联通分量缩点构建新图

新图一定是一个DAG，在这个DAG中，如果最长链的长度=新图的大小，那么就意味着满足了条件

那么我们就可以强连通分量缩点之后，从新图的每一个点出发跑一次dp最长路找出最长链，判断是否为新图的大小

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;

const int maxn=1050,maxm=6050;
struct edge{int to,next;}e[maxm],e2[maxm];
int last[maxn],last2[maxn],belong[maxn],opt[maxn];
int dfn[maxn],low[maxn],flag[maxn],q[maxn];
int n,m,dfn_tot,scc_tot,top,et,et2,f,t;

inline void addedge(int u,int v){e[++et].to=v;e[et].next=last[u];last[u]=et;}
inline void addedge2(int u,int v){e2[++et2].to=v;e2[et2].next=last2[u];last2[u]=et2;}
inline void makenothing(){
    memset(last,0,sizeof(last));memset(last2,0,sizeof(last2));
    memset(belong,0,sizeof(belong));memset(flag,0,sizeof(flag));
    memset(opt,-1,sizeof(opt));memset(q,0,sizeof(q));
    memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
    scc_tot=dfn_tot=et=et2=top=f=0;
}

void tarjan(int x){
    low[x]=dfn[x]=++dfn_tot;
    flag[x]=1;q[++top]=x;
    for(int i=last[x];i;i=e[i].next)
        if (!dfn[e[i].to]){tarjan(e[i].to);low[x]=min(low[x],low[e[i].to]);}
        else if (flag[e[i].to]) low[x]=min(low[x],dfn[e[i].to]);
    if (low[x]==dfn[x]){
        scc_tot++;
        int now=0;
        while(now!=x){
            now=q[top--];
            belong[now]=scc_tot;
            flag[now]=0;
        }
    }
}
int dp(int x){  
    if (opt[x]!=-1) return opt[x];  
    int sum=0;  
    for (int i=last2[x];i;i=e2[i].next) sum=max(sum,dp(e2[i].to));    
    opt[x]=++sum;  
    return sum;  
}  
int main(){
    scanf("%d",&t);
    while(t--){
        makenothing();
        scanf("%d%d",&n,&m);
        For(i,1,m){
            int x,y;scanf("%d%d",&x,&y);
            addedge(x,y);
        }
        For(i,1,n) if (!dfn[i]) tarjan(i);
        For(u,1,n)
            for(int i=last[u];i;i=e[i].next)
                if (belong[u]!=belong[e[i].to]) addedge2(belong[u],belong[e[i].to]);
        int ans=0;
        For(i,1,scc_tot) ans=max(ans,dp(i));
        if (ans==scc_tot) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}