洛谷P3144 [USACO16OPEN]关闭农场关闭农场
离线的反着的并查集
看看在不在一个集合内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#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
int n,m;
int f[99999],a[3009][3099],b[3999];
int ans[19999];
int find(int x)
{
if(x==f[x])return x;
int fx=find(f[x]);
return f[x]=fx;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a[x][y]=1;
a[y][x]=1;
}
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
for(int i=n;i>=1;i--)
{
int fx=find(b[i]);
for(int j=i;j<=n;j++)
if(a[b[i]][b[j]])
{
int fy=find(b[j]);
f[fy]=fx;
}
int w=0,fz=0;
for(int j=i;j<=n;j++)
{
fz=find(b[j]);
if(w!=fz&&w!=0) ans[i]++;
w=fz;
}
}
for(int i=1;i<=n;i++)
if(ans[i])printf("NO\n");
else printf("YES\n");
}
poj 1984导航噩梦
带权并查集
不过我就是过不了
请大佬给我找错2333
思路:
维护横坐标和纵坐标
通过输入的x-x1,y-y1
判断 父节点与父节点的距离
合并父节点
1 | #include<cstdio> |