感谢@JCarlson 为我找题&翻译

求一个图是否任意两点i,j都可以到达(从i到j或从j到i)

解法:

scc缩环,然后拓扑排序判定是否是唯一的拓扑序列

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct edge
{
    int y;
    edge * next;
};
edge * li[1005];
edge * li2[1005];
int top=0;
edge * new_edge()
{
    static edge a[100005];
    return &a[top++];
}
void insert_edge(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
void insert_edge_2(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li2[x];
    li2[x]=t;
}
int dfn[1005];
int low[1005];
int inque[1005];
int belong_to[1005];
int num;
int newn;
bool flag;
void scc(int x)
{
    static int top=0;
    static int que[1005];
    que[top++]=x;
    inque[x]=true;
    dfn[x]=num++;
    low[x]=dfn[x];
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (dfn[t->y]==-1)
        {
            scc(t->y);
            low[x]=min(low[x],low[t->y]);
        }
        else if (inque[t->y])
        {
            low[x]=min(low[x],dfn[t->y]);
        }
    }
    if (low[x]==dfn[x])
    {
        for (;;)
        {
            top--;
            belong_to[que[top]]=newn;
            inque[que[top]]=false;
            if (que[top]==x) break;
        }
        newn++;
    }
}
int in[1005];
void topo_sort()
{
    int i;
    for (i=0;i<newn;i++)
    {
        edge * t;
        for (t=li2[i];t!=0;t=t->next)
        {
            in[t->y]++;
        }
    }
    static int que[1005];
    int front=0,rail=0;
    for (i=0;i<newn;i++)
    {
        if (in[i]==0) que[rail++]=i;
    }
    for (;front<rail;front++)
    {
        if (rail-front>=2) flag=false;
        edge * t;
        for (t=li2[que[front]];t!=0;t=t->next)
        {
            in[t->y]--;
            if (in[t->y]==0)
            {
                que[rail++]=t->y;
            }
        }
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int i;
        memset(li,0,sizeof(li));
        memset(li2,0,sizeof(li2));
        top=0;
        num=0;
        newn=0;
        for (i=0;i<m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x--;
            y--;
            insert_edge(x,y);
        }
        memset(dfn,-1,sizeof(dfn));
        for (i=0;i<n;i++)
        {
            if (dfn[i]==-1) scc(i);
        }
        for (i=0;i<n;i++)
        {
            edge * t;
            for (t=li[i];t!=0;t=t->next)
            {
                if (belong_to[i]==belong_to[t->y]) continue;
                insert_edge_2(belong_to[i],belong_to[t->y]);
            }
        }
        flag=true;
        topo_sort();
        if (flag)
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    return 0;
}