组织

solution

20分

缩环,暴力判\(DAG\)中的点两两之间连通性.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define M 105
#define N 100005
using namespace std;
typedef long long ll;
struct graph{
    int nxt,to;
}e[N];
int g[N],f[N],l[N],r[N],s[N],to[M],dfn[N],low[N],n,m,t,top,cnt;
bool a[M][M],ins[N];
queue q;
inline int read(){
    int ret=0;char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        ret=(ret<<1)+(ret<<3)+c-'0';
        c=getchar();
    }
    return ret;
}
inline void addedge(int x,int y){
//  printf("%d %d\n",x,y);
    e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;
}
inline void tarjan(int u){
    dfn[u]=low[u]=++cnt;
    s[++top]=u;ins[u]=true;
    for(int i=g[u];i;i=e[i].nxt)
        if(!dfn[e[i].to]){
            tarjan(e[i].to);
            low[u]=min(low[u],low[e[i].to]); 
        }
        else if(ins[e[i].to])
            low[u]=min(low[u],low[e[i].to]); 
    if(dfn[u]==low[u])
        while(s[top+1]!=u){
            f[s[top]]=u;
            ins[s[top--]]=false; 
        }
}
inline void bfs(){
    int u;cnt=0;
    for(int i=1;i<=n;++i)
        if(!to[i]) q.push(i);
    while(!q.empty()){
        s[++cnt]=u=q.front();q.pop();
        for(int i=g[u];i;i=e[i].nxt)
            if(!(--to[e[i].to]))
                q.push(e[i].to);
    }
    for(u=s[cnt--];cnt>=0;u=s[cnt--])
        for(int i=g[u];i;i=e[i].nxt){
            a[u][e[i].to]=true;
            for(int j=1;j<=n;++j)
                a[u][j]|=a[e[i].to][j];
        }
}
inline void Aireen(){
    scanf("%d",&n);
    scanf("%d",&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&l[i],&r[i]);
        addedge(l[i],r[i]);
    }
    cnt=0;
    for(int i=1;i<=n;++i)
        if(!dfn[i]) tarjan(i);
    if(n<=100){
        cnt=0;
        memset(g,0,sizeof(g));
        for(int i=1;i<=m;++i)
            if(f[l[i]]!=f[r[i]]){
                addedge(f[l[i]],f[r[i]]);++to[r[i]];
            }
        bfs(); 
        scanf("%d",&t);
        for(int i=1,j,k;i<=t;++i){
            scanf("%d%d",&j,&k);
            if(f[j]==f[k]||a[f[j]][f[k]]){
                puts("NO");return;
            }
        }
        puts("YES"); 
        printf("%d\n",m);
        for(int i=1;i<=m;++i)
            printf("%d %d\n",l[i],r[i]);
        return;
    }
    scanf("%d",&t);
    for(int i=1,j,k;i<=t;++i){
        scanf("%d%d",&j,&k);
        if(f[j]!=f[k]){
            puts("NO");return;
        }
    }
    puts("YES"); 
    printf("%d\n",m);
    for(int i=1;i<=m;++i)
        printf("%d %d\n",l[i],r[i]);
}
int main(){
    freopen("gplt.in","r",stdin);
    freopen("gplt.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

100分

缩环,分块,用\(bitset\)求出所有点到这一块的点的连通性,判是否可行.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define M 10000
#define N 100005
#define min(a,b) a a[N];
inline int read(){
    int ret=0;char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        ret=(ret<<1)+(ret<<3)+c-'0';
        c=getchar();
    }
    return ret;
}
inline void addedge(int x,int y){
    e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;
}
int f[N],s[N],dfn[N],low[N],top;bool ins[N];
inline void tarjan(int u){
    dfn[u]=low[u]=++cnt;
    s[++top]=u;ins[u]=true;
    for(int i=g[u];i;i=e[i].nxt)
        if(!dfn[e[i].to]){
            tarjan(e[i].to);
            low[u]=min(low[u],low[e[i].to]); 
        }
        else if(ins[e[i].to])
            low[u]=min(low[u],low[e[i].to]); 
    if(dfn[u]==low[u])
        while(s[top+1]!=u){
            f[s[top]]=u;
            ins[s[top--]]=false; 
        }
}
int to[N],q[N],h,t;
inline void topo(){
    int u;h=1;
    for(int i=1;i<=n;++i)
        if(!to[i]) q[++t]=i;
    while(h<=t){
        u=q[h++];
        for(int i=g[u];i;i=e[i].nxt)
            if(!(--to[e[i].to])) q[++t]=e[i].to;
    }
}
inline void func(int b,int end){
    for(int i=1;i<=n;++i)
        a[i].reset();
    for(int i=b;i<=end;++i)
        a[i][i-b+1]=1;
    for(int i=t;i;--i)
        for(int j=g[q[i]];j;j=e[j].nxt)
            a[q[i]]|=a[e[j].to]; 
}
inline void Aireen(){
    n=read();m=read();
    for(int i=1;i<=m;++i){
        l[i]=read();r[i]=read();
        addedge(l[i],r[i]); 
    }
    cnt=0;
    for(int i=1;i<=n;++i)
        if(!dfn[i]) tarjan(i);
    memset(g,0,sizeof(g));cnt=0;
    for(int i=1;i<=m;++i)
        if(f[l[i]]!=f[r[i]]){
            addedge(f[l[i]],f[r[i]]);++to[r[i]];
        }
    topo();
    k=read();
    for(int i=1;i<=k;++i){
        x[i]=read();y[i]=read();
        if(f[x[i]]==f[y[i]]){
            puts("NO");return;
        }
    }
    for(int i=0;i*M+1<=n;++i){
        func(i*M+1,(i+1)*M); 
        for(int j=1;j<=k;++j)
            if(y[j]>i*M&&y[j]<=(i+1)*M&&a[x[j]][y[j]-i*M]){
                puts("NO");return;
            }
    }
    puts("YES"); 
    printf("%d\n",m);
    for(int i=1;i<=m;++i)
        printf("%d %d\n",l[i],r[i]);
}
int main(){
    freopen("gplt.in","r",stdin);
    freopen("gplt.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}