题目描述
balabala
并查集例题
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define N 666
int m, n, x, y;
char c;
struct node{
int x, y;
}f[N][N], k1, k2;//k1为线段起始点,k2为终点
node find(node k)//查找祖先(并查集模板)
{
if(f[k.x][k.y].x == k.x && f[k.x][k.y].y == k.y)
return k;
else f[k.x][k.y] = find(f[k.x][k.y]);
return f[k.x][k.y];
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
f[i][j].x = i, f[i][j].y = j;//建图
for(int i = 1; i <= m; i++){
cin >> x >> y >> c;
k1 = find(f[x][y]);
if(c == 'D')
k2 = find(f[x + 1][y]);//下画x+1
if(c == 'R')
k2 = find(f[x][y + 1]);//右画y+1
if(k1.x == k2.x && k1.y == k2.y){//在同一集合则画线后必联通
cout << i << endl;
return 0;//输出步数,退出
}else f[k1.x][k1.y] = k2;//不在同一集合则继续画线,合并祖先
}
printf("draw\n");//最终没有闭合
return 0;
}