1.題目說明

小明正在做一個網絡實驗。

他設置了?n?臺電腦，稱為節點，用于收發和存儲數據。

初始時，所有節點都是獨立的，不存在任何連接。

小明可以通過網線將兩個節點連接起來，連接后兩個節點就可以互相通信了。

兩個節點如果存在網線連接，稱為相鄰。

小明有時會測試當時的網絡，他會在某個節點發送一條信息，信息會發送到每個相鄰的節點，之后這些節點又會轉發到自己相鄰的節點，直到所有直接或間接相鄰的節點都收到了信息。

所有發送和接收的節點都會將信息存儲下來。

一條信息只存儲一次。

給出小明連接和測試的過程，請計算出每個節點存儲信息的大小。

2.輸入格式

輸入的第一行包含兩個整數?n,m，分別表示節點數量和操作數量。

節點從?1?至?n?編號。

接下來?m?行，每行三個整數，表示一個操作。

（1）如果操作為 1 a b ，表示將節點?a?和節點?b?通過網線連接起來。當 a = b 時，表示連接了一個自環，對網絡沒有實質影響。

（2）如果操作為 2 p t ，表示在節點?p?上發送一條大小為?t?的信息。

3.輸出格式

輸出一行，包含?n?個整數，相鄰整數之間用一個空格分割，依次表示進行完上述操作后節點?1?至節點?n?上存儲信息的大小。

4.數據范圍

1≤n≤10000,
1≤m≤10的5次方,
1≤t≤100

5.輸入樣例

4 8
1 1 2
2 1 10
2 3 5
1 4 1
2 2 2
1 1 2
1 2 4
2 2 1

6.輸出樣例

13 13 5 3

7.代碼

// 1.合并時不創建新點
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 10010;int n, m;
int p[N], d[N];int find(int x)
{if (p[x] == x || p[p[x]] == p[x]) return p[x];int r = find(p[x]);d[x] += d[p[x]];p[x] = r;return r;
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ ) p[i] = i;while (m -- ){int t, a, b;scanf("%d%d%d", &t, &a, &b);if (t == 1){a = find(a), b = find(b);if (a != b){d[a] -= d[b];p[a] = b;}}else{a = find(a);d[a] += b;}}for (int i = 1; i <= n; i ++ )if (i == find(i)) printf("%d ", d[i]);else printf("%d ", d[i] + d[find(i)]);puts("");return 0;
}// 2.合并時創建新點
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110010;int n, m;
int p[N], d[N];int find(int x)
{if (p[x] != x){if (p[p[x]] == p[x]) return p[x];int r = find(p[x]);d[x] += d[p[x]];p[x] = r;}return p[x];
}int main()
{scanf("%d%d", &n, &m);for (int i = 0; i < N; i ++ ) p[i] = i;int k = n;while (m -- ){int t, a, b;scanf("%d%d%d", &t, &a, &b);if (t == 1){a = find(a), b = find(b);if (a != b){k ++ ;p[a] = p[b] = k;}}else{a = find(a);d[a] += b;}}for (int i = 1; i <= n; i ++ )if (i == find(i)) printf("%d ", d[i]);else printf("%d ", d[i] + d[find(i)]);return 0;
}