栗子栗子

小trick之倒跑并查集

倒跑并查集

算法介绍:

并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。

这是百度百科上对于并查集的解释。

顾名思义,仅仅只有多元素的合并以及查询其属于哪个集合的操作(注意并没有拆分),这就是并查集。

并查集的应用很多

例如以前做过一道BFS染色的题目(求一个矩阵中连通块的数目),这就可以用并查集来实现。

此处不一一列举了。

离线,区别于在线

在线要求对于已知的数据,每给出一个查询需要立即给出其对应的结果。

而离线与之相反,可以将所有的查询统一记录保存,并利用查询之间的关系减小求解的复杂度。

最后统一输出所有查询的结果。

这是一个十分有用的trick,多应用于大量的查询之中。

trick级应用

倒跑并查集可以广泛应用于仅具有拆分操作的多操作多查询问题。

很多时候若干个元素构成的集合具有一些性质,例如连通性,区间和等等。

但是题目需要将一些大集合拆分成若干个小集合,并有多次拆分。

与此同时还有多次查询的内容,询问你某些元素或者某些集合是否具有对应的性质。

此时一般可以使用倒跑并查集的算法。

即先按要求记录下所有的操作和查询,并按操作将集合全部拆开。

然后反向进行给定的操作,不断地利用并查集进行一些元素或集合的合并。

一般情况下,此时询问的性质将呈现出不会消失的状态

(即某集合具有某些性质,其合并后新集合具有与之对应的性质或可由原性质轻易递推而来)

这时再对所有的查询进行应答,记录答案,并最终输出。

例题(题面点击链接)

CodeForces 722C

思路:

先将所有数均置为destroyed,每次合并集合可O(1)求和,用此和维护max即可

CCCC L2-013

思路:

每次将点与与其相连的所有未删除点进行合并,若合并次数>1,则该点为割点

HDU 5652

思路:

二维并查集,每次合并指定格子以及与其相邻的格子,判断第一行及最后一行是否有格子位于同一集合即可。

另,此题并查集需做些小修改,详见代码。

代码

CodeForces 722C

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
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

const int maxn=100005;

bool vis[maxn];
int fat[maxn];
LL sum[maxn];
LL ans[maxn];
LL a[maxn];
int ord[maxn];

int i,j,k,l,m,n;
LL ma;

int find(int x)
{
if(fat[x]==x)return x;
else return fat[x]=find(fat[x]);
}

void hb(int x,int y)
{
int xx=find(x);
int yy=find(y);
fat[yy]=fat[xx];
sum[xx]+=sum[yy];
}

int main()
{
memset(vis,0,sizeof(vis));
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
for(i=1;i<=n;i++)scanf("%d",&ord[i]);
for(i=1;i<=n;i++)
{
sum[i]=a[i];
fat[i]=i;
}
ma=0;
for(i=n;i>=1;i--)
{
ans[i]=ma;
int v=ord[i];
vis[v]=true;
ma=max(ma,sum[find(v)]);
if(vis[v+1])
{
hb(v,v+1);
ma=max(ma,sum[find(v)]);
}
if(vis[v-1])
{
hb(v,v-1);
ma=max(ma,sum[find(v)]);
}
}
for(i=1;i<=n;i++)printf("%lld\n",ans[i]);
return 0;
}

CCCC L2-013

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<cstdio>
#include<cstring>
#include<vector>

using namespace std;

const int maxn=505;

int i,j,k,l,m,n;
bool vis[maxn];
int fat[maxn],sum[maxn];
int ord[maxn],ans[maxn];
vector<int> g[maxn];

int find(int t)
{
if(fat[t]==t)return t;
else return fat[t]=find(fat[t]);
}

bool hb(int x)
{
int f=0;
for(unsigned int i=0;i<g[x].size();i++)
{
int y=g[x][i];
if(vis[y])continue;
int xx=find(x);
int yy=find(y);
if(xx==yy)continue;
f++;
fat[yy]=xx;
sum[xx]+=sum[yy];
}
return f>1;
}

int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&j,&k);
g[j].push_back(k);
g[k].push_back(j);
}
memset(vis,0,sizeof(vis));
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d",&ord[i]);
vis[ord[i]]=true;
}
for(i=0;i<n;i++)
{
fat[i]=i;
sum[i]=1;
}
for(i=0;i<n;i++)
if(!vis[i])hb(i);
for(i=m;i>=1;i--)
{
vis[ord[i]]=false;
bool flag=hb(ord[i]);
if(flag)ans[i]=-1;else ans[i]=1;
}
for(i=1;i<=m;i++)
{
if(ans[i]>0)printf("City %d is lost.\n",ord[i]);
else printf("Red Alert: City %d is lost!\n",ord[i]);
}
if(m==n)printf("Game Over.");
return 0;
}

HDU5652

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
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

struct father
{
int x,y;
father(int x=0,int y=0):x(x),y(y){}
bool operator == (struct father p)const
{return x==p.x && y==p.y;}
}fat[505][505];

int a[505][505];
int ord[505*505][2];
char s[505];

int i,j,k,l,m,n,t,T;

father find(int x,int y)
{
if(fat[x][y].x==x && fat[x][y].y==y)return fat[x][y];
else return fat[x][y]=find(fat[x][y].x,fat[x][y].y);
}

void hb(int x1,int y1,int x2,int y2)
{
father f1=find(x1,y1);
father f2=find(x2,y2);
if(f1==f2)return;
if(f1.x<f2.x)
{
fat[f2.x][f2.y]=f1;
}else
{
fat[f1.x][f1.y]=f2;
}
}

bool IsHb(father w,father e)
{
father f1=find(w.x,w.y);
father f2=find(e.x,e.y);
return f1==f2;
}

bool law(int x,int y)
{
if(x<1 || x>n)return false;
if(y<1 || y>m)return false;
if(a[x][y]==1)return false;
return true;
}

int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d\n",&n,&m);
for(i=1;i<=n;i++)
{
gets(s);
for(j=1;j<=m;j++)a[i][j]=s[j-1]-48;
}
scanf("%d",&t);
for(i=1;i<=t;i++)
{
scanf("%d%d",&ord[i][0],&ord[i][1]);
ord[i][0]++;ord[i][1]++;
a[ord[i][0]][ord[i][1]]=1;
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
fat[i][j].x=i,fat[i][j].y=j;
for(i=1;i<=n;i++)
for(j=2;j<=m;j++)
if(a[i][j]==0 && a[i][j-1]==0)
hb(i,j-1,i,j);
for(i=2;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i-1][j]==0 && a[i][j]==0)
hb(i-1,j,i,j);
for(i=t;i>=1;i--)
{
bool f=false;
for(j=1;j<=m;j++)
if(find(n,j).x==1){f=true;break;}
if(f)break;
int x=ord[i][0];
int y=ord[i][1];
a[x][y]=0;
if(law(x-1,y))hb(x-1,y,x,y);
if(law(x+1,y))hb(x,y,x+1,y);
if(law(x,y-1))hb(x,y-1,x,y);
if(law(x,y+1))hb(x,y,x,y+1);
}
if(i==0)
{
bool f=false;
for(j=1;j<=m;j++)
if(find(n,j).x==1){f=true;break;}
if(!f){printf("0\n");continue;}
}
if(i==t)printf("-1\n");else printf("%d\n",i+1);
}
return 0;
}