@[Joseph_H](/user/568775)
find这么写
```cpp
int find(int u){
return s[u] = s[u] == u ? u : find(s[u]);
}
```
by _NTT_ @ 2021-12-30 15:55:26
谢谢
by Joseph_H @ 2021-12-30 15:58:21
为什么改了之后T3个wa1个？
```
#include<bits/stdc++.h>
using namespace std;
const int NUM = 5e3 + 1;
int s[NUM];
void look(){
printf("what happen?\n");
}
struct node{
int u,v,w;
node(int _u,int _v,int _w){
u = _u;
v = _v;
w = _w;
}
};
vector <node> v;
int find(int u){
return s[u] == u ? u : find(s[u]);
}
inline int read(){
int now = 0,nev = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') nev = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
now = (now << 1) + (now << 3) + (c & 15);
c = getchar();
}
return now * nev;
}
int n,m;
bool cmp(node a,node b){
return a.w < b.w;
}
int kruskal(){
int ans = 0;
for(int i = 1;i <= n;i++){
s[i] = i;
}
stable_sort(v.begin(),v.end(),cmp);
for(int i = 0;i < m;i++){
int b = find(v[i].u);
int c = find(v[i].v);
if(b == c) continue;
s[c] = b;
ans += v[i].w;
}
printf("%d",ans);
}
int main(){
n = read();
m = read();
for(int i = 1;i <= m;i++){
int a = read(),b = read(),c = read();
v.push_back(node(a,b,c));
}
kruskal();
}
```
by Joseph_H @ 2021-12-30 16:06:54
@[Joseph_H](/user/568775)
```cpp
int find(int u){
return s[u] == u ? u : find(s[u]);
}
```
这样的find没有路径压缩，写成这样：
```cpp
int find(int u){
return s[u] == u ? u : s[u] = find(s[u]);
}
```
by _NTT_ @ 2021-12-30 16:15:38
@[Joseph_H](/user/568775) 另外没有判断图是否联通
by _NTT_ @ 2021-12-30 16:16:39
```
#include<bits/stdc++.h>
using namespace std;
const int NUM = 5e3 + 1;
int s[NUM];
void look(){
printf("what happen?\n");
}
struct node{
int u,v,w;
node(int _u,int _v,int _w){
u = _u;
v = _v;
w = _w;
}
};
vector <node> v;
int find(int u){
return s[u] == u ? u : s[u] = find(s[u]);
}
inline int read(){
int now = 0,nev = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') nev = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
now = (now << 1) + (now << 3) + (c & 15);
c = getchar();
}
return now * nev;
}
int n,m;
bool cmp(node a,node b){
return a.w < b.w;
}
void kruskal(){
int ans = 0;
for(int i = 1;i <= n;i++){
s[i] = i;
}
stable_sort(v.begin(),v.end(),cmp);
for(int i = 0;i < m;i++){
int b = find(v[i].u);
int c = find(v[i].v);
if(b == c) continue;
s[c] = b;
ans += v[i].w;
}
int flag = s[1];
for(int i = 1;i <= n;i++){
if(flag != s[i]){
printf("orz");
return;
}
// printf("%d ",s[i]);
}
printf("\n%d",ans);
}
int main(){
n = read();
m = read();
for(int i = 1;i <= m;i++){
int a = read(),b = read(),c = read();
v.push_back(node(a,b,c));
}
kruskal();
}
```
改成这样就变成只A一个了
by Joseph_H @ 2021-12-30 16:27:29
@[违规用户名TWnOO6x*](/user/397282)
by Joseph_H @ 2021-12-30 16:27:49
如果联通的话，最后所有的s[i]都会一样的。
by Joseph_H @ 2021-12-30 16:28:59
把最后的printf("\n%d",ans); 改成printf("%d",ans);后变成wa2个\
~~换行严判的luogu就是离谱~~
by Joseph_H @ 2021-12-30 16:32:51
好吧我是小丑
最后改为
```
int flag = find(1);
for(int i = 1;i <= n;i++){
if(flag != find(i)){
printf("orz");
return;
}
}
```
然后就AC了
by Joseph_H @ 2021-12-30 16:34:54