题目概述

问一张 $n$ 个点 $m$ 条有向边的图是否满足两两点 $x,y$ 之间均有 $x$ 与 $y$ 连通或 $y$ 与 $x$ 连通。

解题报告

FFF团还管这么多？不是直接烧吗？显然一个强连通分量里的点均满足，所以可以缩起来。

然后就变成DAG了，观察一下一条链的情况是绝对满足的，而有些分叉的情况是不满足的。

实际上只有同层分叉才会导致不满足（因为这样的话不可能到达），这个层指的就是拓扑序。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000,maxm=6000<<1;

int te,n,m,ti,dfn[maxn+5],low[maxn+5],top,stk[maxn+5],SCC[maxn+5];
int E,lnk[2][maxn+5],nxt[maxm+5],son[maxm+5];bool instk[maxn+5];
int que[maxn+5],D[maxn+5],dis[maxn+5];

#define Add(ID,x,y) (son[++E]=(y),nxt[E]=lnk[ID][x],lnk[ID][x]=E)
void Tarjan(int x){
    dfn[x]=low[x]=++ti;stk[++top]=x;instk[x]=true;
    for (int j=lnk[0][x];j;j=nxt[j])
        if (!dfn[son[j]]) Tarjan(son[j]),low[x]=min(low[x],low[son[j]]);
        else if (instk[son[j]]) low[x]=min(low[x],dfn[son[j]]);
    if (dfn[x]==low[x])
        for (int y=(SCC[0]++,stk[top--]);;y=stk[top--])
            {SCC[y]=SCC[0];instk[y]=false;if (x==y) break;}
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        scanf("%d%d",&n,&m);E=0;memset(lnk,0,sizeof(lnk));
        for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),Add(0,x,y);
        ti=0;memset(dfn,0,sizeof(dfn));SCC[0]=0;
        for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i);
        for (int i=1;i<=n;i++)
            for (int j=lnk[0][i];j;j=nxt[j])
                if (SCC[i]!=SCC[son[j]]) Add(1,SCC[i],SCC[son[j]]),D[SCC[son[j]]]++;
        int Head=0,Tail=0;for (int i=1;i<=SCC[0];i++) if (!D[i]) que[++Tail]=i,dis[i]=0;
        while (Head!=Tail)
            for (int x=que[++Head],j=lnk[1][x];j;j=nxt[j])
                if (!(--D[son[j]])) que[++Tail]=son[j],dis[son[j]]=dis[x]+1;
        sort(dis+1,dis+1+SCC[0]);for (int i=1;i<SCC[0];i++) if (dis[i]==dis[i+1]) goto FFF;
        puts("I love you my love and our love save us!");continue;FFF:puts("Light my fire!");
    }
    return 0;
}