为什么按照第一篇题解的按照输入顺序两两配对建图是对的,但是先把x坐标排序,按顺序连边是错的(y坐标也一样,见代码),会WAon18

正确代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=500005;
struct node
{
	int x;
	int y;
	int num;
}p[N];
vector<node> zx[N],zy[N];
bool cmp1(node p1,node p2)
{
	if(p1.x!=p2.x)
	return p1.x<p2.x;
	else if(p1.y!=p2.y)
	return p1.y<p2.y;
	else
	return p1.num<p2.num;
}
bool cmp2(node p1,node p2)
{
	if(p1.y!=p2.y)
	return p1.y<p2.y;
	else if(p1.x!=p2.x)
	return p1.x<p2.x;
		else
	return p1.num<p2.num;
}
vector<int> G[N];
void add(int u,int v)
{
	G[u].push_back(v);
	G[v].push_back(u);
}
int col[N];
void dfs(int a)
{
	for(int to:G[a])
	{
		if(col[to])
		continue;
		col[to]=col[a]^3;
		dfs(to);
	}
}
int gx[N],gy[N];
signed main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>p[i].x>>p[i].y;
		p[i].num=i;
		if(!gx[p[i].x])
		gx[p[i].x]=p[i].num;
		else
		{
			add(gx[p[i].x],p[i].num);
			gx[p[i].x]=0;
		}
		if(!gy[p[i].y])
		gy[p[i].y]=p[i].num;
		else
		{
			add(gy[p[i].y],p[i].num);
			gy[p[i].y]=0;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!col[i])
		{
		col[i]=1;
		dfs(i);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(col[i]==0)
		cout<<"WA";
		if(col[i]==1)
		cout<<"r";
		if(col[i]==2)
		cout<<"b";
	}
	return 0;
}

错误代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=500005;
struct node
{
	int x;
	int y;
	int num;
}p[N];
vector<node> zx[N],zy[N];
bool cmp1(node p1,node p2)
{
	if(p1.x!=p2.x)
	return p1.x<p2.x;
	else if(p1.y!=p2.y)
	return p1.y<p2.y;
	else
	return p1.num<p2.num;
}
bool cmp2(node p1,node p2)
{
	if(p1.y!=p2.y)
	return p1.y<p2.y;
	else if(p1.x!=p2.x)
	return p1.x<p2.x;
		else
	return p1.num<p2.num;
}
vector<int> G[N];
void add(int u,int v)
{
	G[u].push_back(v);
	G[v].push_back(u);
}
int col[N];
void dfs(int a)
{
	for(int to:G[a])
	{
		if(col[to])
		continue;
		col[to]=col[a]^3;
		dfs(to);
	}
}
signed main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>p[i].x>>p[i].y;
		p[i].num=i;
	}
	for(int i=1;i<=n;i++)
	zx[p[i].x].push_back(p[i]);
	for(int i=1;i<=n;i++)
	zy[p[i].y].push_back(p[i]);
	for(int i=1;i<=200000;i++)
	{
		sort(zx[i].begin(),zx[i].end(),cmp2);
	//	cout<<"*"<<i<<" "<<(zx[i].size())<<endl;
		if(!zx[i].size())
		continue;
		for(int j=0;j<zx[i].size()-1;j++)
		{
	//	cout<<"x"<<zx[i][j].num<<" "<<zx[i][j+1].num<<endl;
		add(zx[i][j].num,zx[i][j+1].num);
		}
	}
	for(int i=1;i<=200000;i++)
	{
		sort(zy[i].begin(),zy[i].end(),cmp1);
		if(!zy[i].size())
		continue;	
		for(int j=0;j<zy[i].size()-1;j++)
		{
	//	cout<<"y"<<zy[i][j].num<<" "<<zy[i][j+1].num<<endl;
		add(zy[i][j].num,zy[i][j+1].num);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!col[i])
		{
		col[i]=1;
		dfs(i);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(col[i]==0)
		cout<<"WA";
		if(col[i]==1)
		cout<<"r";
		if(col[i]==2)
		cout<<"b";
	}
	return 0;
}