AcWing算法提高课【第四章高级数据结构】并查集

分析：

显然，当出现闭环的时候，就会出现我们当前节点和要到达的节点出现一个闭环

代码：

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int N = 210;
 6 
 7 int n, m;
 8 int g[N][N], tot;
 9 int f[N * N];
10 
11 int get(int x)
12 {
13   return f[x] == x ? x : f[x] = get(f[x]);
14 }
15 int main()
16 {
17   cin >> n >> m;
18   for (int i = 1; i <= n; i ++ ) 
19     for (int j = 1; j <= n; j ++ )
20       g[i][j] = ++ tot;
21 
22   for (int i = 1; i <= n * n; i ++ ) f[i] = i;
23   
24   for (int i = 1; i <= m; i ++ )
25   {
26     int a, b; 
27     char op[2];
28     cin >> a >> b >> op;
29 
30     int x = g[a][b], y;
31     if (*op == 'D')
32         y = g[a + 1][b];
33     else 
34         y = g[a][b + 1];
35     
36     x = get(x), y = get(y);
37     if (x == y) 
38     {
39       cout << i << endl;
40       return 0;
41     }
42     f[x] = y;
43   }
44   
45   cout << "draw" << endl;
46   
47   return 0;
48 }

View Code

1252. 搭配购买

分析：

显然，彩云被捆绑了。通过并查集捆绑，祖宗节点为fa[x] == x

打包后就是一个0/1背包了。判断是否取当前的祖宗节点。

代码：

 1 #include <cstdio>
 2 #include <cmath>
 3 
 4 using namespace std;
 5 
 6 const int N = 10010;
 7 
 8 int n, m, t;
 9 int v[N], w[N];
10 int fa[N];
11 int dp[N];
12 
13 int get(int x)
14 {
15     return fa[x] == x ? x : fa[x] = get(fa[x]);
16 }
17 int main()
18 {
19     scanf("%d%d%d", &n, &m, &t);
20     for (int i = 1; i <= n; i ++ )
21     {
22         fa[i] = i;
23         scanf("%d%d", &v[i], &w[i]);
24     }
25     
26     while (m -- ) 
27     {
28         int x, y; scanf("%d%d", &x, &y);
29         x = get(x);
30         y = get(y);
31         if (x == y) continue;
32         fa[x] = y;
33         v[y] += v[x];
34         w[y] += w[x];
35     }
36     
37     for (int i = 1; i <= n; i ++ )
38         if (i == fa[i])
39             for (int j = t; j >= v[i]; j -- ) 
40                 dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
41     
42     printf("%d
", dp[t]);
43     
44     return 0;
45 }

View Code