• API
• FAQ
• Tools
• Archive
SHARE
TWEET

Untitled

a guest Feb 27th, 2020 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. const int N = 2 * 100100;
2. int p[N], sz[N];
3. void init()
4. {
5.     for (int i = 0; i < N; i++)
6.         p[i] = i, sz[i] = 1;
7. }
8.
9. int find_set(int v)
10. {
11.     if (v == p[v])
12.         return v;
13.     return p[v] = find_set(p[v]);
14. }
15.
16. void union_set(int a, int b)
17. {
18.     a = find_set(a);
19.     b = find_set(b);
20.     if (a != b)
21.     {
22.         if (sz[a] < sz[b])
23.             swap(a, b);
24.         p[b] = a;
25.         sz[a] += sz[b];
26.     }
27. }
28.
29. vector<vector<pii>>g;
30. vector<pair<int, pii>> e;
31. vector<int> pr;
32. vector<int>lvl;
33. vector<vector<int>>jump;
34. vector<vector<int>>maxW;
35.
36. int n, m;
37. int LOG = 20;
38.
39. void inputGraph()
40. {
41.     cin >> n >> m;
42.     g = vector<vector<pii>>(n);
43.     pr = vector<int>(n);
44.     lvl = vector<int>(n);
45.     jump = vector<vector<int>>(n, vector<int>(LOG));
46.     maxW = vector<vector<int>>(n, vector<int>(LOG));
47.     for (int i = 0; i < m; i++)
48.     {
49.         int u, v, w;
50.         cin >> u >> v >> w;
51.         u--, v--;
52.
53.         e.pb({ w,{u,v} });
54.         g[v].pb({ u,w });
55.         g[u].pb({ v,w });
56.     }
57. }
58.
59. void solve()
60. {
61.     init();
62.     inputGraph();
63.
64. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top