暴力 7/10
$O(N*M) = 1e9$
原来做错就是,在找同一个集合里的节点时写成了p[i] == x
,错了,找的是祖宗节点,而不是父节点。
#include <iostream>
using namespace std;
const int N = 10010;
int p[N], n, q; //p:祖宗节点编号
int cnt[N]; //每个节点的信息大小
int find(int x)
{
return p[x] == x ? x : p[x] = find(p[x]);
}
int main()
{
cin >> n >> q;
for (int i = 1; i <= n; i++) p[i] = i;
int op, a, b;
while (q--)
{
cin >> op >> a >> b;
if (op == 1)
{
int pa = find(a), pb = find(b);
if (pa != pb)
p[pb] = pa;
}
else
{
int pa = find(a); //祖宗
for (int i = 1; i <= n; i++)
if (find(i) == pa) //若祖宗等于这个点
cnt[i] += b;
}
}
for (int i = 1; i <= n; i++) cout << cnt[i] << ' ';
return 0;
}
路径压缩
$O(N)$
#include <iostream>
using namespace std;
const int N = 10010;
int p[N], n, q; //p[x]:父节点
int d[N]; //每个点的最终真实权值
int find(int x) //路径压缩,返回这个节点的真实值,即到根节点的权值之和,d[x] = d[p[x]] + d[root]
{
//若是根节点或父节点就是根节点,直接返回。
//若父节点就是根节点,就会加上两次根节点的值
if (p[x] == x || p[p[x]] == p[x]) return p[x];
int root = find(p[x]); //祖宗节点
d[x] += d[p[x]]; //一直加上父节点的值
p[x] = root;
return root;
}
int main()
{
cin >> n >> q;
for (int i = 1; i <= n; i++) p[i] = i;
int op, a, b;
while (q--)
{
cin >> op >> a >> b;
if (op == 1) //合并a, b
{
int pa = find(a), pb = find(b);
if (pa != pb)
{
//a合并到b,b为祖宗节点,a的值减去b
d[pa] -= d[pb];
p[pa] = pb;
}
}
else //a 与其并查集加上b
{
d[find(a)] += b; //根节点加上b
}
}
for (int i = 1; i <= n; i++)
if (find(i) == i) //每个并查集的根节点
cout << d[i] << ' ';
else cout << d[i] + d[find(i)] << ' '; //这个节点到根节点的权值加上根节点的权值
return 0;
}