题解 P4575 【[CQOI2013]图的逆变换】

ix35 · 2020-02-04 19:45:09 · 题解

大致思路就是：如果在图 D 中：u\to v\to w，又有 x\to v\to w，那么在 E 中，uv，xv 都向 vw 连边。此时如果存在另一个 y 使得 v\to y 有边，则在 E 中 uv，xv 都应该向 vy 有边。

也就是说，两个点指向一个公共的点，那么它们所有出边指向的点集必然相同，事实上这是存在 D 的充要条件，证明不难。

之前几篇题解要么用了并查集，要么用了数组暴力判断，这里提供一种不难想且速度不慢的方法：Bitset。

用 Bitset 记录邻接矩阵，枚举两行，算一下两行的与和异或，如果与不为 0，则说明指向公共点，此时再看异或，如果异或不为 0，说明出边不重合，答案为 No.

#include <bits/stdc++.h>
using namespace std;
const int MAXN=310;
int t,n,m,x,y;
bitset <MAXN> b[MAXN],tmp1,tmp2;
int main () {
    scanf("%d",&t);
    for (int ii=1;ii<=t;ii++) {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) {b[i].reset();}
        for (int i=1;i<=m;i++) {
            scanf("%d%d",&x,&y);
            x++,y++;
            b[x].set(y);
        }
        int flg=0;
        for (int i=1;i<=n;i++) {
            if (flg) {break;}
            for (int j=1;j<=n;j++) {
                tmp1=b[i]&b[j],tmp2=b[i]^b[j];
                if (tmp1.count()!=0&&tmp2.count()!=0) {flg=1;break;}
            }
        }
        printf("%s\n",flg?"No":"Yes");
    }
    return 0;
}