@[清风居士](/user/443739) ,本人认为是可以的,先建边,并查集判断连通性
by RAYMOND_7 @ 2021-08-06 16:16:36
这做法是错误的
举例:
```
3 2
1 2 2
1 2
1 3
```
本是无解,程序会输出 $2$ 或 $3$。
```cpp
//fake method
#include<algorithm>
#include<cstdio>
const int maxn=301;
int n,m,u,v;
struct Node{
int h,size,id;
}a[maxn];
bool operator<(Node a,Node b){
return a.h>b.h;
}
int fa[maxn],size[maxn];
int find(int a){
return a==fa[a]?a:find(fa[a]);
}
void merge(int a,int b){
a=find(a),b=find(b);
if(a==b)return;
if(size[a]<size[b])a^=b^=a^=b;
fa[b]=a;
size[a]+=size[b];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].h),a[i].id=i;
fa[i]=i,size[i]=1;
}
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
if(a[u].h!=a[v].h)merge(u,v);
}
for(int i=1;i<=n;i++)a[i].size=size[find(i)];
std::sort(a+1,a+n+1);
int std=a[1].h;
int i=1;
while(a[i].h==std){
if(a[i].size==n){
puts("Oui, j'ai trouve la solution.");
printf("%d",a[i].id);
return 0;
}else i++;
}
puts("Non");
return 0;
}
```
by 2019zll @ 2021-09-27 19:28:45
因为这是有向边,不能用并查集维护
by 2019zll @ 2021-09-27 19:29:27
eee有一说一, 不用想那么复杂
by QAQeee @ 2023-02-17 18:50:35