ABC327D题解

· · 题解

题意

给定 n 个值为 0 或 1 的点和 m 条关系，每一条关系表示两个点的值不能相同，问是否有合法构造方案满足所有条件。

Sol

因为值只有 0 或 1 两种，对于每一种关系 \{a_i,b_i\} 可以类比成 「a_i 为 1 且 b_i 为 0」，以及「a_i 为 0 且 b_i 为 1」 这样的形式，于是该题就变成了 2-SAT 问题。

具体解法大概是对于一个节点 u，我们设 u 表示该节点为 1 ，u+n 表示该节点为 0，或者说前者的反面 。

对于「a_i 为 1 且 b_i 为 0」这样的关系，只需要建一条有向边 a_i \to b_i+n，表示「若 a_i 为 1 则 b_i 一定为 0」。同理 「a_i 为 0 且 b_i 为 1」建一条有向边 a_i+n \to b_i，表示「若 a_i 为 0 则 b_i 一定为 1」。

这样我们得到了一张有向图，只需要在这张有向图上跑 Tarjan 求强连通分量，同一强连通分量的点取值是相同的（a_i=b_i+n 意味着 a_i \neq b_i ）。

最后只需要对于每个点判断 u 和 u+n 是否在同一强连通分量内就可以了，如果在显然是不满足题意的（u=u+n ，u \neq u ？，不可能我不等于我自己）。

时间复杂度 O(n+m)

Code

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define ll long long
#define N 2000005
#define endl "\n" 
#define fi first
#define se second
using namespace std;
const ll mod=1e9+7;
ll low[N],dfn[N],cnt,vis[N],bel[N];
stack <ll> q;
ll ans;
ll a[N],b[N];
vector<ll> v[N];
ll n,m;
void tarjan(ll x){
    low[x]=dfn[x]=++cnt;
    q.push(x);
    vis[x]=1;
    for(auto y:v[x]){
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(vis[y]) low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x]){
        ans++;
        while(1){
            auto t=q.top();
            bel[t]=ans;
            vis[t]=0;
            q.pop();
            if(t==x)break;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>b[i];
        v[a[i]].push_back(b[i]+n);// a为1则b为0
        v[a[i]+n].push_back(b[i]);// a为0且b为1
    }
    for(int i=1;i<=n*2;i++)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;i++){
        if(bel[i]==bel[i+n]){//判断i所属强连通分量和i+n所属强连通分量相同
            cout<<"No\n";
            return 0;
        }
    }
    cout<<"Yes\n";
    return 0;
}

拓展

Q：如果让我们输出合法的方案，应该怎样做呢？

A：考虑每个点 0 和 1 的关系，对缩完点的图（每个点代表原图中的一个强连通分量）进行拓扑排序，若 u 所在强连通分量的拓扑序 小于 u+n 所在强连通分量的拓扑序，则说明取 u=0 才符合条件，反之 u=0。如果等于呢？那就在同一个强连通分量里面同时 取0 和 1才符合条件直接无解了。

进行 Tarjan 得到的强连通分量编号便是反着的拓扑序（越靠近开始节点的编号越大），所以若 u 所在强连通分量的编号小于 u+n 所在强连通分量的编号，u=1 即可。

for(int i=1;i<=n;i++){
    if(bel[i]==bel[i+n]){
        cout<<"No\n";
        return 0;
    }
    if(bel[i]<bel[i+n])res[i]=1;
}
cout<<"Yes\n";
for(int i=1;i<=n;i++)cout<<res[i]<<" ";