大概率因为 Python 慢
by XYY1411 @ 2021-04-10 16:12:36
@[zzuBobby](/user/497577) 你这个并查集写的不对
by lcyxds @ 2021-04-10 16:37:20
@[XYY1411](/user/129562) 不是的，改了并查集就过了
by lcyxds @ 2021-04-10 16:37:41
@[zzuBobby](/user/497577)
```python
def find(u):
if S[u] == u:
return u
else:
return find(S[u])
```
改成
```python
def find(u):
if S[u] == u:
return u
else:
S[u] = find(S[u])
return S[u]
```
不加路径压缩的并查集复杂度是 $O(MN)$，自然过不去
by lcyxds @ 2021-04-10 16:44:35
@[zzuBobby](/user/497577) 不过你那个程序我改成了 C++ 还真的跑过去了。。。洛谷数据是真的水
by lcyxds @ 2021-04-10 17:20:04
```cpp
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
struct Edge{
int U;
int V;
int W;
void _init_(int u, int v, int w){
U = u;
V = v;
W = w;
}
};
bool cmpW (const Edge a, const Edge b){
return a.W < b.W;
}
vector<int> S;
vector<Edge> edge;
vector<Edge> s_edge;
int n;
int m;
int find(int u){
if (S[u] == u)
return u;
else
return find(S[u]);
}
int kruskal(){
int ans = 0;
int bound = 0;
// 并查集初始化
for (int i = 1; i < n+1; i++){
S[i] = i;
}
// 每次寻找最短且无环边
s_edge = edge;
sort(s_edge.begin(), s_edge.end(), cmpW);
for (int i = 1; i < m+1; i++){
int b = find(s_edge[i].U);
int c = find(s_edge[i].V);
if (b == c)
continue;
else {
S[c] = b;
ans += s_edge[i].W;
bound += 1;
if (bound == (n - 1))
break;
}
}
return ans;
}
int main() {
scanf("%d%d", &n, &m); // 点数 边数
Edge un;
un.U = 0, un.V = 0, un.W = 0;
if (m >= (n - 1)){ // 连通
// 并查集定义
S.reserve(n+1);
// 边集的定义
edge.push_back(un);
for (int i = 1; i < m+1; i++){
Edge t;
scanf("%d%d%d", &t.U, &t.V, &t.W);
edge.push_back(t);
}
// 调用算法
int res = kruskal();
printf("%d", res);
}
else
printf("orz");
}
```
复杂度 $O(MN)$ 居然跑过了
by lcyxds @ 2021-04-10 17:21:54
@[lcyxds](/user/124314) 首先非常感谢您的回复，已经顺利AC，因为这道题是我在C语言算法书上看到的，所以将C(C++)的代码改成了python所以没有通过。
另外还请您不吝赐教，我看不懂
```
return find(S[u])
```
和
```
S[u] = find(S[u])
return S[u]
```
的区别……
(很有意思的回复验证码，WQ3Q ^^)
by zzuBobby @ 2021-04-10 21:41:47
@[zzuBobby](/user/497577) `S[u]=find(S[u])` 是路径压缩。
如果使用 `return find(S[u])`，相当于不断暴力向上跳父亲，最坏情况下每次查询复杂度可能达到 $\Theta(n)$，而且可以卡满。
而如果使用路径压缩，相当于每次查询时都将自己的父亲定义为自己的祖先，这时不会出现多次查询 $\Theta(n)$ 的情况，总算法复杂度是 $O(m\log_{1+m/n}n)$的。
by lcyxds @ 2021-04-11 07:00:49
@[lcyxds](/user/124314) 收到！以后用return会尽量一步到位的
by zzuBobby @ 2021-04-11 11:32:19