poj 2793 Cactus

本文从WordPress迁移而来, 查看全部WordPress迁移文章

无向图仙人掌图判定(LCA + TreeDp) + 计算无向图仙人掌图有多少个生成子图

详细分析请看

仙人掌图的判定

步骤:

  1. 建无向图
  2. dfs无向图,过程中

    保存树边,即建好dfs树,可以直接建成有根树,而不是无根树,这样更方便

    记录节点在树中的深度,代码中深度从1开始计数

    保存所有的成环边,成环边的保存有讲究。每一条成环边,实际上就是一个LCA询问

  3. 得到dfs树和所有LCA询问,利用tarjan解决LCA询问
  4. 做好树DP的初始化工作,然后进行树DP

    可以一直做完整个树DP过程,但我代码中设置了剪枝,当遇到dp[u] >= 2的时候返回false

    意味着该边属于2个或更多的环中。但是发现剪枝后时间没啥变化,好像更慢了……….

  5. 经过以上步骤就可以判断这个图是不是一个cactus了,如果是,下面就计算cactus的生成子图
  6. 生成子图:跟原图的顶点一样并且连通。

    为了保证连通,原cactus中,不属于环的边一定要保留(否则图断裂)

    一个环内的边,最多只能去掉1条边,去掉2条或以上,环断裂

    一个环如果有m条边,去掉1条边的方案就有m种。另外可以1条边都不去掉,保存原样。所以一个环内的方案数是m+1

    每个环都这样,按照乘法原理,就可以知道原图有多少个生成cactus了

  7. 结果很大,最后的乘法原理计算要用高精度

注意:在我的代码思路中,成环边的保存要讲究。在建立无向图的时候,是把无向边拆分成2条有向边保存的,所以对于一条成环边,会遇到两次。一条成环边,相当于后来的一个LCA询问,在保存LCA询问的时候也是拆分为2个来保存了,所以成环边保存了2次,询问也会重复。所以约定,遇到成环边时,如果是从反边的方向走的,忽略掉,如果是从正边的方向走的,才保存

成环边保存过程,在代码的dfs函数中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs(int m ,int u ,int fa ,int depth){ //无向图的遍历函数,m这个参数有用处
vis[u] = true;
num++; //统计访问了多少个点
dep[u] = depth;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
if(!vis[v]){
ver[u].pb(v); //建立dfs树,有根数,方向确定
dfs(k,v,u,depth+1);
}
else{ //
if(v == fa && m^1 == k) //反边,回到父亲的,跳过
continue;
else{ //一条成环边(u,v)
if(k & 1) continue;//成环边的的反边,只保留正边,否则询问会重复
add_ask(u,v); //拆分保存成环边,相当于一个LCA询问
add_ask(v,u); //拆分保存成环边,相当于一个LCA询问
}
}
}
}

这题跑了2000+ms,修改后居然更慢了跑到了3000ms,不知道那些跑了200ms的是怎么做到的

这题的数据输入方式也很特别,在写完这份代码后才想到,可能这样的方式是方便这题求解的,可以避免掉一些无用功,但是暂时没有想到更好的解决方法

代码比较长,有比较详细的注释

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
using namespace std;
#define N 20010
#define M 1000010
#define cl memset
#define pb push_back

int n,tot,num;
vector<int>ver[N]; //建dfs树
int head[N]; //建图
struct edge{ //建图
int v,next;
}e[M];
int dep[N]; //节点在dfs树中点的深度
bool vis[N]; //标记数组
int p[N]; //用于tarjan并查集
int list[N],tota; //保存LCA询问
struct ask{ //保存LCA询问
int u,v,lca,next;
}ea[M];
int dp[N]; //dp数组
int ans[N],len; //高精度保存最后结果

inline void add(int u ,int v){
e[tot].v = v;
e[tot].next = head[u];
head[u] = tot++;
}

inline void add_ask(int u,int v){
ea[tota].u = u;
ea[tota].v = v;
ea[tota].lca = -1;
ea[tota].next = list[u];
list[u] = tota++;
}

void dfs(int m ,int u ,int fa ,int depth){ //无向图的遍历函数,m这个参数有用处
vis[u] = true;
num++; //统计访问了多少个点
dep[u] = depth;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
if(!vis[v]){
ver[u].pb(v); //建立dfs树,有根数,方向确定
dfs(k,v,u,depth+1);
}
else{ //
if(v == fa && m^1 == k) //反边,回到父亲的,跳过
continue;
else{ //一条成环边(u,v)
if(k & 1) continue; //成环边的的反边,只保留正边,否则询问会重复
add_ask(u,v); //拆分保存成环边,相当于一个LCA询问
add_ask(v,u); //拆分保存成环边,相当于一个LCA询问
}
}
}
}

int find(int x){
return x == p[x] ? x : p[x] = find(p[x]);
}

void tarjan(int u){
vis[u] = true;
for(int i = 0; i < ver[u].size(); i++){
int v = ver[u][i];
tarjan(v);
p[v] = u; //合并集合,将v所在集合并到父亲u中
}
for(int k = list[u]; k != -1; k = ea[k].next){
int v = ea[k].v;
if(vis[v]) //可以回答LCA询问
ea[k].lca = ea[k^1].lca = find(v);
}
}

void LCA(){
for(int i=1; i<=n; i++){
p[i] = i; //并查集初始化
vis[i] = false;
}
tarjan(1);
}

bool DP(int u){
for(int i = 0; i < ver[u].size(); i++){
int v = ver[u][i];
if( !DP(v) ) return false;
dp[u] += dp[v];
if(dp[u] >= 2) return false;
}
return true;
}

bool treedp(){
cl(dp,0,sizeof(dp));
for(int i = 0; i < tota; i += 2){
dp[ea[i].u]++;
dp[ea[i].v]++;
dp[ea[i].lca] -= 2;
}
return DP(1);
}

void bignum(int m){ //高精度计算答案
int c = 0;
for(int i = 0; i < len; i++){
ans[i] = ans[i] * m + c;
c = ans[i] / 10;
ans[i] %= 10;
}
while(c){
ans[len++] = c % 10;
c /= 10;
}
}

void cal(){
len = 1; ans[0] = 1;
for(int i = 0; i < tota; i += 2){ //查看每个询问,也就是每个环
int m = dep[ea[i].u] + dep[ea[i].v]
- 2 * dep[ea[i].lca] + 1; //一个环内有多少条边
bignum(m + 1);
}
for(int i = len - 1; i >= 0; i--)
printf("%d",ans[i]);
printf("\n");
}

void solve(){
for(int i=1; i<=n; i++){
list[i] = -1;
vis[i] = false;
ver[i].clear();
}
bool cactus = true;
num = 0;
dfs(-1,1,-1,1); //从点1开始遍历整个图
if(num < n)
cactus = false; //还有点没有访问,说明无向图不连通
if(!cactus){
puts("0");
return ;
}
LCA();
if( !treedp() ){
puts("0");
return ;
}
cal();
}

int main(){
int m;
while(scanf("%d%d",&n,&m)!=EOF){
tot = tota = 0;
cl(head,-1,sizeof(head));
while(m--){
int num,u,v;
scanf("%d",&num);
scanf("%d",&u);
for(int i=1; i<num; i++){
scanf("%d",&v);
add(u,v);
add(v,u);
u = v;
}
}
solve();
}
return 0;
}