二维并查集,y总的思路是二维变一维,我是直接用pair做
本题思路为:若起点和它能走到的点已在一个集合,break。否则不断把起点和它走到的点加入同一集合中
#include <iostream>
#include <cstring>
#define x first
#define y second
using namespace std;
int n,m;
const int N=210,M=25000;
typedef pair<int,int> pii;
pii p[N][N];
pii find(int x,int y)
{
if(x!=p[x][y].x || y!=p[x][y].y) p[x][y]=find(p[x][y].x,p[x][y].y);
return p[x][y];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
p[i][j]={i,j};
}
}
int res=0;
for(int i=1;i<=m;i++)
{
int a,b;;
char op;
cin>>a>>b>>op;
//把(a,b)和接下来走到的点,放到同一个集合
int pa=find(a,b).x;
int pb=find(a,b).y;
//cout<<pa<<" "<<pb<<endl;
int new_a,new_b;
if(op=='D')
{
new_a=a+1;
new_b=b;
}
else
{
new_a=a;
new_b=b+1;
}
int new_pa=find(new_a,new_b).x;
int new_pb=find(new_a,new_b).y;
//cout<<new_pa<<" "<<new_pb<<"....."<<endl;
if(new_pa==pa && new_pb==pb)
{
res=i;
break;
}
//把新点和旧点加入到一个集合中(ps:只涉及一条边的两个端点)
p[new_pa][new_pb]={pa,pb};
}
if(res==0) cout<<"draw"<<endl;
else
cout<<res;
return 0;
}
二刷,又是find函数出了问题,还是不太明白
#include <iostream>
#include <cstring>
using namespace std;
const int N=250;
int g[N][N];
typedef pair<int,int> pii;
pii p[N][N];
int n,m;
pii find(int x,int y)
{
if(x!=p[x][y].first || y!=p[x][y].second) p[x][y]=find(p[x][y].first,p[x][y].second);
return p[x][y];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
p[i][j]={i,j};
}
}
int res=0;
for(int i=1;i<=m;i++)
{
int a,b;
char op;
cin>>a>>b>>op;
if(op=='D')
{
int x1=find(a,b).first;
int y1=find(a,b).second;
int x2=find(a+1,b).first;
int y2=find(a+1,b).second;
if(x1==x2 && y1==y2)
{
res=i;
break;
}
else
{
p[x2][y2]=p[a][b];
}
}
else
{
int x1=find(a,b).first;
int y1=find(a,b).second;
int x2=find(a,b+1).first;
int y2=find(a,b+1).second;
if(x1==x2 && y1==y2)
{
res=i;
break;
}
else
{
p[x2][y2]={x1,y1};
}
}
}
if(res==0) cout<<"draw";
else cout<<res;
}
find函数终极模板!!
注意return不要加else!!
return的是p[x]而不能是x!!
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
ii find(int x,int y)
{
if(p[x][y].first != x || p[x][y].second !=y) p[x][y]=find(p[x][y].first,p[x][y].second);
return p[x][y];
}
三刷,算是完全掌握,一遍ac
#include <iostream>
#include <cstring>
using namespace std;
const int N=500;
typedef pair<int,int> pii;
pii p[N][N];
int n,m;
pii find(int x,int y)
{
if(p[x][y].first!=x || p[x][y].second!=y) p[x][y]=find(p[x][y].first,p[x][y].second);
return p[x][y];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
p[i][j]={i,j};
}
}
int flag=0;
for(int i=1;i<=m;i++)
{
int x,y;
char op;
cin>>x>>y>>op;
if(flag) continue;
if(op=='D')
{
int a=find(x+1,y).first;
int b=find(x+1,y).second;
x=find(x,y).first;
y=find(x,y).second;
if(x!=a || y!=b)
{
p[a][b]={x,y};
}
else
{
flag=i;
}
}
else
{
int a=find(x,y+1).first;
int b=find(x,y+1).second;
x=find(x,y).first;
y=find(x,y).second;
if(x!=a || y!=b)
{
p[a][b]={x,y};
}
else
{
flag=i;
}
}
}
if(!flag) cout<<"draw";
else cout<<flag;
return 0;
}
兄弟有时间填个邀请码hhhhhhhhh(可以得AC币,邀请码在学生认证那填) 我的邀请码是:GUDFH