# 7_11_ F题 Infinite Go（并查集）

baidu_19306071 · · 939 次点击 · · 开始浏览

# 7_11_ F题 Infinite Go（并查集）

### 代码

``````#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e4+10;
int mov[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int fa[maxn];
set<pair<int, int> > space[maxn];
map<pair<int ,int>,int>M ,idx;

void init(int n){
for(int i = 0 ; i <= n ; i ++){
fa[i] = i;
space[i].clear();
}
M.clear();
idx.clear();
}

int Find (int x){
return fa[x] == x ? x:fa[x] = Find(fa[x]);
}

void Union(int x,int y){
x = Find(x);
y = Find(y);
if(space[x].size() < space[y].size()) swap(x,y);
fa[y] = x;
for(auto it = space[y].begin() ; it != space[y].end() ; it ++)
space[x].insert(*it);
space[y].clear();
}

inline int getColor(int x,int y){
if(M.find(make_pair(x,y)) == M.end()) return -1;
return M[make_pair(x,y)];
}

void del(pair<int,int> start ,int col){
queue<pair<int,int> > que;
que.push(start);
while(!que.empty()){
auto cur=que.front();
que.pop();
M.erase(cur);
for(int i = 0;i < 4;i++){
int x = cur.first + mov[i][0];
int y = cur.second + mov[i][1];
if(x <= 0 || y <= 0) continue;

auto next = make_pair(x,y);
if(getColor(x,y) == col )
que.push(next);
else if(getColor(x,y) == (col^1))
space[Find(idx[next])].insert(cur);
}
}
}

void put(int x,int y,int col){
auto cur = make_pair(x,y);
M[cur] = col;
for(int i = 0; i < 4; i++){
x = cur.first + mov[i][0];
y = cur.second+ mov[i][1];
if(x <= 0 || y <= 0) continue;

auto next = make_pair(x,y);

if(getColor(x,y) == col)
Union(idx[cur],idx[next]);
else if(getColor(x,y) == -1)
space[Find(idx[cur])].insert(next);
else{
space[Find(idx[next])].erase(cur);
if(space[Find(idx[next])].size() == 0)
del(next,col^1);
}
}
space[Find(idx[cur])].erase(cur);
if(space[Find(idx[cur])].size()==0)
del(cur,col);
}

int main(){
int T,n;
scanf("%d", &T);
while(T --){
scanf("%d",&n);
init(n);
int col = 0;
for(int i = 0 ; i < n ; i ++,col ^= 1){
int x,y;
scanf("%d %d",&x,&y);
idx[make_pair(x,y)] = i+1;
put(x,y,col);
}
int black = 0,white = 0;
for(auto it = M.begin(); it != M.end(); it ++){
if(it->second == 0) black ++;
else white ++;
}
printf("%d %d\n",black,white);
}
return 0;
}``````

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

# 7_11_ F题 Infinite Go（并查集）

### 代码

``````#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e4+10;
int mov[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int fa[maxn];
set<pair<int, int> > space[maxn];
map<pair<int ,int>,int>M ,idx;

void init(int n){
for(int i = 0 ; i <= n ; i ++){
fa[i] = i;
space[i].clear();
}
M.clear();
idx.clear();
}

int Find (int x){
return fa[x] == x ? x:fa[x] = Find(fa[x]);
}

void Union(int x,int y){
x = Find(x);
y = Find(y);
if(space[x].size() < space[y].size()) swap(x,y);
fa[y] = x;
for(auto it = space[y].begin() ; it != space[y].end() ; it ++)
space[x].insert(*it);
space[y].clear();
}

inline int getColor(int x,int y){
if(M.find(make_pair(x,y)) == M.end()) return -1;
return M[make_pair(x,y)];
}

void del(pair<int,int> start ,int col){
queue<pair<int,int> > que;
que.push(start);
while(!que.empty()){
auto cur=que.front();
que.pop();
M.erase(cur);
for(int i = 0;i < 4;i++){
int x = cur.first + mov[i][0];
int y = cur.second + mov[i][1];
if(x <= 0 || y <= 0) continue;

auto next = make_pair(x,y);
if(getColor(x,y) == col )
que.push(next);
else if(getColor(x,y) == (col^1))
space[Find(idx[next])].insert(cur);
}
}
}

void put(int x,int y,int col){
auto cur = make_pair(x,y);
M[cur] = col;
for(int i = 0; i < 4; i++){
x = cur.first + mov[i][0];
y = cur.second+ mov[i][1];
if(x <= 0 || y <= 0) continue;

auto next = make_pair(x,y);

if(getColor(x,y) == col)
Union(idx[cur],idx[next]);
else if(getColor(x,y) == -1)
space[Find(idx[cur])].insert(next);
else{
space[Find(idx[next])].erase(cur);
if(space[Find(idx[next])].size() == 0)
del(next,col^1);
}
}
space[Find(idx[cur])].erase(cur);
if(space[Find(idx[cur])].size()==0)
del(cur,col);
}

int main(){
int T,n;
scanf("%d", &T);
while(T --){
scanf("%d",&n);
init(n);
int col = 0;
for(int i = 0 ; i < n ; i ++,col ^= 1){
int x,y;
scanf("%d %d",&x,&y);
idx[make_pair(x,y)] = i+1;
put(x,y,col);
}
int black = 0,white = 0;
for(auto it = M.begin(); it != M.end(); it ++){
if(it->second == 0) black ++;
else white ++;
}
printf("%d %d\n",black,white);
}
return 0;
}``````