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问题

题目背景

若某个条件是ab

这个题的关键是将非ab连接,非ba连接。我们在这个题先分配状态,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;
}