图的连通性与2-SAT

用户头像 发布于 2025-08-11 44 次阅读 OI

S+图的连通性与2-SAT

A. 校园网

注意到强连通分量内的点肯定是符合的，所以进行缩点，
第一问很容易能想到答案是缩点后图内无入度的点，
而第二问可以发现一定要将所有无出度的点和无入度的点相连，
所以答案就是缩点后图中无入度的点的数量和无出度的点的数量的最大值。
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,x;
int dfn[N],low[N],idx,cnt,siz[N],vis[N];
int in[N],out[N];
stack <int> s;
vector<int> g[N];
void tj(int x){
    dfn[x]=low[x]=++idx;
    s.push(x);
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i];
        if(!dfn[v]){
            tj(v);
            low[x]=min(low[x],low[v]);
        }
        else if(!vis[v])
            low[x]=min(low[x],low[v]);
    }
    if(dfn[x]==low[x]){
        cnt++;
        while(1){
            int y=s.top();s.pop();
            vis[y]=cnt;
            siz[cnt]++;
            if(y==x) break;
        }
    }

}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) while(cin>>x&&x) g[i].push_back(x);
    for(int i=1;i<=n;i++) if(!dfn[i]) tj(i);
    for(int i=1;i<=n;i++) {
        for(int j=0;j<g[i].size();j++){
            int u=i,v=g[u][j];
            if(vis[u]!=vis[v]){
                in[vis[v]]++;
                out[vis[u]]++;
            }
        }
    }
    int ans1=0,ans2=0;
    for(int i=1;i<=cnt;i++){
        if(!in[i]) ans1++;
        if(!out[i]) ans2++;
    }
    if(cnt==1){
        cout<<"1\n0";
        return 0;
    }
    cout<<ans1<<endl<<max(ans1,ans2);
    return 0;
}
C++

B. Going from u to v or from v to u?

大致题意：判断一个图内任意两点能否互相到达。
很容易想到先缩点，
将原图变为有向无环图以后，
判断最长链长度是否等于强连通分量数即可，
可以用bfs跑一遍图，$dp_v=max(dp_v,dp_u+1)$。
代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n,m;
int dfn[N],low[N],vis[N],is[N];
int dp[N],in[N],ans=1;
int T,idx,cnt;
stack<int> s;
vector<int> g[N],g1[N];
queue<int> q;
void tj(int x){
    dfn[x]=low[x]=++idx;
    s.push(x);
    is[x]=1;
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i];
        if(!dfn[v]){
            tj(v);
            low[x]=min(low[x],low[v]);
        }
        else if(is[v])
            low[x]=min(low[x],low[v]);
    }
    if(dfn[x]==low[x]){
        cnt++;
        while(1){
            int y=s.top();s.pop();
            is[y]=0;
            vis[y]=cnt;
            if(y==x) break;
        }
    }
}
int main(){
    cin>>T;
    while(T--){
        idx=0,cnt=0,ans=1;
        memset(dfn,0,sizeof dfn);
        memset(dfn,0,sizeof low);
        memset(dfn,0,sizeof vis);
        memset(dfn,0,sizeof is);
        memset(dfn,0,sizeof dp);
        memset(dfn,0,sizeof in);
        while(s.size()) s.pop();
        while(q.size()) q.pop();
        for(int i=0;i<N;i++) g[i].clear(),g1[i].clear();
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            int u,v;
            cin>>u>>v;
            g[u].push_back(v);
        }
        for(int i=1;i<=n;i++) if(!dfn[i]) tj(i);
        for(int u=1;u<=n;u++) for(int i=0;i<g[u].size();i++){
            int v=g[u][i];
            if(vis[u]!=vis[v]){
                g1[vis[u]].push_back(vis[v]);
                in[vis[v]]++;
            }
        }
        for(int i=1;i<=cnt;i++) if(!in[i]) q.push(i),dp[i]=1;
        while(q.size()){
            int u=q.front();
            q.pop();
            for(int i=0;i<g1[u].size();i++){
                int v=g1[u][i];
                dp[v]=max(dp[v],dp[u]+1);
                ans=max(ans,dp[v]);
                if(!(--in[v])) q.push(v); 
            }
        }
        if(ans==cnt) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}
C++

C. 自行车道 Bike paths

由题可知，
缩点后原图绝对会变成 $x$ 颗树，
所以可以直接dfs，
其中size表示强连通分量的大小：
$dp_u=\sum(dp_v)+size_u$
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int n,m;
int dfn[N],low[N],vis[N],is[N],siz[N];
int dp[N],ans;
int idx,cnt;
stack<int> s;
vector<int> g[N],g1[N];
void tj(int x){
    dfn[x]=low[x]=++idx;
    s.push(x);
    is[x]=1;
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i];
        if(!dfn[v]){
            tj(v);
            low[x]=min(low[x],low[v]);
        }
        else if(is[v]){
            low[x]=min(low[x],low[v]);
        }

    }
    if(dfn[x]==low[x]){
        cnt++;
        while(1){
            int y=s.top();s.pop();
            is[y]=0;
            vis[y]=cnt;
            siz[cnt]++;
            if(y==x) break;
        }
    }

}
void dfs(int u){
    if(dp[u]) return;
    for(int i=0;i<g1[u].size();i++){
        int v=g1[u][i];
        dfs(v);
        dp[u]+=dp[v];
    }
    dp[u]+=siz[u];
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tj(i);
    for(int u=1;u<=n;u++){
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i];
            if(vis[u]!=vis[v]){
                g1[vis[u]].push_back(vis[v]);
            }
        }
    }
    for(int i=1;i<=cnt;i++) if(!dp[i]) dfs(i);
    for(int i=1;i<=n;i++) cout<<dp[vis[i]]-1<<endl;
    return 0;
}
C++

D. 稳定婚姻

不难发现，
当我们将有关系的男女建边后，
不安全的婚姻的夫妻二人都在同一个环内，
所以可以想到强连通分量，
所以我们要把无向边转化为有向边，
又因为婚姻破裂时总是男生去与女生“旧情复燃”，
所以对于结婚的夫妻，由妻子指向丈夫，
对于曾经的情侣，由男生指向女生，
判断夫妻二人是否在同一个强连通分量内即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,idx,cnt;
int dfn[N],low[N];
int vis[N],is[N],tag[N];
stack<int> s;
vector<int> g[N];
map<string,int> mp;
void tj(int x){
    dfn[x]=low[x]=++idx;
    s.push(x);
    is[x]=1;
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i];
        if(!dfn[v]){
            tj(v);
            low[x]=min(low[x],low[v]);
        }
        else if(is[v]) low[x]=min(low[x],low[v]);
    }
    if(dfn[x]==low[x]){
        cnt++;
        while(1){
            int y=s.top();s.pop();
            vis[y]=cnt,is[y]=0;
            if(y==x) break;
        }
    }

}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        string x,y;
        cin>>x>>y;
        mp[x]=i,mp[y]=i+n;
        g[i].push_back(i+n);
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        string x,y;
        cin>>x>>y;
        g[mp[y]].push_back(mp[x]);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tj(i);
    int y=1;
    for(int i=1;i<=n;i++){
        if(vis[i]==vis[i+n]) cout<<"Unsafe\n";
        else cout<<"Safe\n";
    } 
    return 0;
}
C++

E. Festival

可以想到差分约束建图：
对于限制1，$u$ ${\underrightarrow{-1}}$ $v$，$v$ ${\underrightarrow{1}}$ $u$
对于限制2，$u$ ${\underrightarrow{0}}$ $v$
那么所有限制1相连的点肯定构成强连通分量，
而所有边权为0的边可以想象成可以无限拉长，
所以不同强连通分量内的点肯定不会重复，
所以计算出每个强连通分量内两点最短路的最大值的和即可。
代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int v,w;
};
const int N=605;
int n,m1,m2,idx,cnt;
int dfn[N],low[N];
int vis[N],is[N],tag[N];
int dis[N][N],ans[N],ans1;
stack<int> s;
vector<node> g[N];
map<string,int> mp;
void tj(int x){
    dfn[x]=low[x]=++idx;
    s.push(x);
    is[x]=1;
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i].v;
        if(!dfn[v]){
            tj(v);
            low[x]=min(low[x],low[v]);
        }
        else if(is[v]) low[x]=min(low[x],low[v]);
    }
    if(dfn[x]==low[x]){
        cnt++;
        while(1){
            int y=s.top();s.pop();
            vis[y]=cnt,is[y]=0;
            if(y==x) break;
        }
    }

}
int main(){
    cin>>n>>m1>>m2;
    memset(dis,0x3f,sizeof dis);
    for(int i=1;i<=n;i++) dis[i][i]=0;
    for(int i=1;i<=m1;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back((node){v,-1});
        g[v].push_back((node){u,1});
        dis[u][v]=min(dis[u][v],-1);
        dis[v][u]=min(dis[v][u],1);
    }
    for(int i=1;i<=m2;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back((node){v,0});
        dis[u][v]=min(dis[u][v],0);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tj(i);
    for(int k=1;k<=n;k++) for(int i=1;i<=n;i++){
        if(vis[i]!=vis[k]) continue;
        for(int j=1;j<=n;j++){
            if(vis[j]!=vis[k]) continue;
            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
        }
    }
    for(int i=1;i<=n;i++) if(dis[i][i]){
        cout<<"NIE";
        return 0;
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
        if(vis[i]!=vis[j]) continue;
        ans[vis[i]]=max(ans[vis[i]],dis[i][j]);
    }
    for(int i=1;i<=cnt;i++) ans1+=ans[i]+1;
    cout<<ans1;
    return 0;
}
C++

F. 通讯网破坏

可以发现一些性质：

  1. 当 $M$ 不是割点时，肯定不满足，因为图还是连通的。
  2. 当 $S$ 和 $T$ 在同一个点双时，肯定也不满足，因为肯定存在另一条路径。
  3. 当将原图缩点后（缩为圆方图）， $M$ 不在 $S$ 到 $T$ 最短路径上时，肯定也不满足。

综上，我们需要求出原图的割点、点双，
并在圆方图上求lca判断 $M$ 在不在 $S$ 到 $T$ 最短路径上。
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=4e4+5;
int n,m,q;
int dfn[N],low[N],tag[N],idx,cnt;
int gd[N],vis[N];
int fa[N][25],d[N];
stack<int> s;
vector<int> g[N],t[N],ans[N];
void tj(int x,int root){
    dfn[x]=low[x]=++idx;
    s.push(x);
    int child=0;
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i];
        if(!dfn[v]){
            child++;
            tj(v,root);
            low[x]=min(low[x],low[v]);
            if(low[v]>=dfn[x]&&x!=root) tag[x]=1;
            if(low[v]>=dfn[x]){
                cnt++;
                while(1){
                    int y=s.top();
                    s.pop();
                    ans[cnt].push_back(y);
                    if(y==v) break;
                }
                ans[cnt].push_back(x);
            }
        }
        else low[x]=min(low[x],dfn[v]);
    }
    if(child>=2&&x==root) tag[x]=1; 
    if(x==root&&child==0){
        cnt++;
        ans[cnt].push_back(x);
        if(!s.empty()&&s.top()==x) s.pop();
    }
}
void dfs(int u,int f){
    fa[u][0]=f;
    d[u]=d[f]+1;
    for(int i=1;i<=20;i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int i=0;i<t[u].size();i++){
        int v=t[u][i];
        if(v==f) continue;
        dfs(v,u);
    }
}
int lca(int u,int v){
    if(d[u]<d[v]) swap(u,v);
    for(int i=20;i>=0;i--){
        if(d[fa[u][i]]>=d[v]){
            u=fa[u][i];
        }
    }
    if(u==v) return u;
    for(int i=20;i>=0;i--){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]){
        while(!s.empty()) s.pop();
        tj(i,i);
    }
    cin>>q;
    int idx1=cnt;
    for(int i=1;i<=n;i++) if(tag[i]) gd[i]=++idx1;
    for(int i=1;i<=cnt;i++){
        for(int j=0;j<ans[i].size();j++){
            int v=ans[i][j];
            if(tag[v]){
                t[i].push_back(gd[v]);
                t[gd[v]].push_back(i);
            }
            else vis[v]=i;
        }
    }
    for(int i=1;i<=idx1;i++){
        if(!d[i]){
            d[i]=1;
            dfs(i,0);
        }
    }
    while(q--){
        int s1,t1,m1;
        cin>>s1>>t1>>m1;
        if(!tag[m1]){
            cout<<"no\n";
            continue;
        }
        s1=tag[s1]?gd[s1]:vis[s1];
        t1=tag[t1]?gd[t1]:vis[t1];
        if(s1==t1){
            cout<<"no\n";
            continue;
        }
        m1=gd[m1];
        int l=lca(s1,t1);
        int l2=lca(s1,m1);
        int l3=lca(t1,m1);
        if((l2==m1&&l3==l)||(l3==m1&&l2==l)) cout<<"yes\n";
        else cout<<"no\n";
    }
    return 0;
}
C++