Si_Yue小屋
0%

连通性问题

发表于 分类于

无向图的边双连通分量

无向图的边双连通分量指的是图中的某子图，删去某条边后，其中的两点还是可以互相到达。在无向图中，按照dfs序的处理是不会遇到横叉边的，所以不用单独考虑。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>

using namespace std;

const int MAXN=200;

struct edge{
    int u,v;
    bool operator<(const edge& other)const{
        if(u==other.u)return v<other.v;
        return u<other.u;
    }
};

vector<int> p[MAXN];
vector<edge> e;
stack<int> st;
int n,m,dfn[MAXN],low[MAXN],bel[MAXN],cnt,idx;

void add(int u,int v){
    p[u].push_back(v);
    p[v].push_back(u);
}

void dfs(int x,int fno){
    dfn[x]=low[x]=++cnt;
    st.push(x);
    for(auto v:p[x]){
        if(v==fno)continue;
        if(!dfn[v]){
            dfs(v,x);
            low[x]=min(low[x],low[v]);
            //割边
            if(low[v]>dfn[x])e.push_back({min(x,v),max(x,v)});
        }else{
            low[x]=min(low[x],dfn[v]);
        }
    }
    if(low[x]==dfn[x]){
        //无向图的边双连通分量
        ++idx;
        for(int v=st.top();v!=x;st.pop(),v=st.top()){
            bel[v]=idx;
        }bel[x]=idx,st.pop();
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v;cin>>u>>v;
        add(u,v);
    }
    dfs(1,0);
    sort(e.begin(),e.end());
    for(const auto& ed:e){
        //打印割边
        cout<<ed.u<<" "<<ed.v<<endl;
    }
    return 0;
}

无向图的点双连通分量

无向图的点双连通分量指的是某个子图除去某个点后，其中的其他任意两点依然可以互相到达。很明显存在某些点属于多个点双连通分量，这种点有个性质是去除它后，所在的几个点双连通分量就不可互相到达了，这种点叫做割点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>

using namespace std;

const int MAXN=2e4+2;

int n,m,dfn[MAXN],low[MAXN],cnt,deg[MAXN];

vector<int> p[MAXN];

vector<int> dots[MAXN];
stack<int> st;
int idx;

void add(int u,int v){
    p[u].push_back(v);
    p[v].push_back(u);
}

void dfs(int x,int fno){
    dfn[x]=low[x]=++cnt;
    st.push(x);
    for(auto v:p[x]){
        if(v==fno)continue;
        if(!dfn[v]){
            dfs(v,x);
            low[x]=min(low[x],low[v]);
            if(low[v]>=dfn[x]){
                dots[++idx].push_back(x);
                ++deg[x];
                int vv;
                do{
                    vv=st.top();
                    dots[idx].push_back(vv);
                    ++deg[vv];
                    st.pop();
                }while(vv!=v);
            }
        }else{
            low[x]=min(low[x],dfn[v]);
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;++i){
        cin>>u>>v;
        add(u,v);
    }
    for(int i=1;i<=n;++i){
        if(!dfn[i]){
            dfs(i,0);
            while(!st.empty())st.pop();
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        ans+=deg[i]>1;
    }cout<<ans<<'\n';
    for(int i=1;i<=n;++i){
        if(deg[i]>1){
            cout<<i<<" ";
        }
    }

    // //点双连通分量
    // for(int i=1;i<=idx;++i){
    //     for(auto t:dots[i]){
    //         cout<<t<<" ";
    //     }cout<<'\n';
    // }
    return 0;
}

广义圆方树

广义圆方树指的是将原来图的每一个点双连通分量中的点记作原点，和新建立的方点进行连接的新树。

题目背景

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int MAXN=5e5+2;

int n,m,dfn[MAXN],low[MAXN],cnt,idx,w[MAXN],sz[MAXN],sz_cur;

int st[MAXN],top;

LL ans;

struct G{
    vector<int> p[MAXN];
    void add(int u,int v){
        p[u].push_back(v);
        p[v].push_back(u);
    }
    vector<int>& operator[](int i){
        return p[i];
    }
}graph,crt;

void tarjan(int x,int fno){
    w[x]=-1;++sz_cur;
    dfn[x]=low[x]=++cnt;
    st[++top]=x;
    for(auto v:graph[x]){
        if(v==fno)continue;
        if(!dfn[v]){
            tarjan(v,x);
            low[x]=min(low[x],low[v]);
            if(low[v]>=dfn[x]){
                int vv;++idx;
                do{
                    vv=st[top--];
                    crt.add(idx,vv);
                    ++w[idx];
                }while(vv!=v);
                crt.add(idx,x);
                ++w[idx];
            }
        }else{
            low[x]=min(low[x],dfn[v]);
        }
    }
}

void dfs(int x,int fno){
    sz[x]=x<=n;
    LL cnt=0;
    for(auto v:crt[x]){
        if(v==fno)continue;
        dfs(v,x);
        cnt+=1ll*sz[x]*sz[v];
        sz[x]+=sz[v];
    }
    cnt+=1ll*sz[x]*(sz_cur-sz[x]);
    cnt<<=1;
    ans+=1ll*cnt*w[x];
}

int main(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;++i){
        cin>>u>>v;
        graph.add(u,v);
    }
    idx=n;
    for(int i=1;i<=n;++i){
        if(!dfn[i]){
            tarjan(i,0);
            dfs(i,0);
            top=sz_cur=0;
        }
    }
    cout<<ans<<endl;
    return 0;
}

有向图的强连通分量

有向图的强连通分量指的是两两可以互相到达的子图。下面的代码综合考虑了可能出现的横叉边，正向边和反向边。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e4+2;

int n,m;
int dfn[MAXN],low[MAXN],cnt;
int bel[MAXN],ins[MAXN],siz[MAXN],idx;
int st[MAXN],top;

vector<int> p[MAXN];

void add(int u,int v){
    p[u].push_back(v);
}

void tarjan(int x){
    dfn[x]=low[x]=++cnt;
    ins[st[++top]=x]=1;
    for(auto v:p[x]){
        if(!dfn[v]){
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }else if(ins[v]){
            low[x]=min(low[x],dfn[v]);
        }
    }
    if(low[x]==dfn[x]){
        int v;++idx;
        do{
            ins[v=st[top--]]=0;
            bel[v]=idx;
            ++siz[idx];
        }while(v!=x);
    }
}

int main(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;++i){
        cin>>u>>v;
        add(u,v);
    }
    for(int i=1;i<=n;++i){
        if(!dfn[i])tarjan(i);
    }
    int ans=0;
    for(int i=1;i<=idx;++i){
        //siz>1的强连通分量个数
        ans+=siz[i]>1;
    }cout<<ans<<'\n';
    return 0;
}

2-SAT问题

题目背景

若某个条件是a或b

这个题的关键是将非a与b连接，非b与a连接。我们在这个题先分配状态，1n为\(x_i=0\)，n+12*n为\(x_i=1\)。这样子我们只需要跑一遍缩点（缩点后的图是有向无环图），然后看每一个\(x_i=0\)的状态和\(x_i=1\)的状态的拓扑序，我们创造解只要看拓扑序大的，也就是记录连通分量顺序小的。如果一样，说明强连通分量中出现了矛盾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>

using namespace std;

const int MAXN=2e6+2;

int n,m;
int dfn[MAXN],low[MAXN],cnt;
int bel[MAXN],idx;
int st[MAXN],ins[MAXN],top;

vector<int> p[MAXN];

inline void add(int u,int v){
    p[u].push_back(v);
}

void tarjan(int x){
    dfn[x]=low[x]=++cnt;
    ins[st[++top]=x]=1;
    for(auto v:p[x]){
        if(!dfn[v]){
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }else if(ins[v]){
            low[x]=min(low[x],dfn[v]);
        }
    }
    if(low[x]==dfn[x]){
        int v;++idx;
        do{
            ins[v=st[top--]]=0;
            bel[v]=idx;
        }while(v!=x);
    }
}

vector<int> ans;

int main(){
    cin>>n>>m;
    for(int i=1,u,a,v,b;i<=m;++i){
        cin>>u>>a>>v>>b;
        add(u+(1-a)*n,v+b*n);
        add(v+(1-b)*n,u+a*n);
    }
    for(int i=1;i<=2*n;++i){
        if(!dfn[i])tarjan(i);
    }
    bool flag=true;
    for(int i=1;i<=n;++i){
        if(bel[i]<bel[i+n]){
            ans.push_back(0);
        }else if(bel[i]>bel[i+n]){
            ans.push_back(1);
        }else{
            flag=false;
            break;
        }
    }
    if(flag){
        cout<<"POSSIBLE"<<'\n';
        for(auto i:ans){
            cout<<i<<" ";
        }cout<<'\n';
    }else{
        cout<<"IMPOSSIBLE"<<'\n';
    }
    return 0;
}