Hlg 1748 【并查集】.cpp

题意：

　　n个数编号从1~n..但是并不按顺序排列..

　　现在想把他们互换位置最后得到1~n的序列..

　　两个数可以交换位置的条件是 |i-j| == bi

　　输入：n 表示n个数

　　　　a[1], a[2], a[3]..a[i]..a[n]

　　　　b[1], b[2], b[3]..b[i]..b[n]

思路：

　　并查集..

　　可以这么看..如果两个数在一个集合里，那么这两个数就可以互相交换位置了..

　　所以就按照i+-b[i]把可以交换的位置的数和该数的归在一个集合里..

　　最后查看是否所有要改的数都在一个集合里..

Tips：

　　加的时候加的应该是a[i], 表示把这些数放在一个集合里..

　　最后看是不是要改位置的数正好都在一个集合里..

　　如果把下标放在一个集合里就没有意义了..

Code：

View Code

 1 #include <stdio.h>
 2 #include <cstring>
 3 
 4 int f[110];
 5 int find(int x)
 6 {
 7     return f[x] == x?x:f[x] = find(f[x]);
 8 }
 9 
10 int n;
11 int a[110], b[110];
12 
13 int main()
14 {
15     freopen("in.txt", "r", stdin);
16     bool flag;
17     while (~scanf("%d", &n)) {
18         flag = true;
19         for (int i = 1; i <= n; ++i)
20             f[i] = i;
21         for (int i = 1; i <= n; ++i)
22             scanf("%d", &a[i]);
23         for (int i = 1; i <= n; ++i)
24             scanf("%d", &b[i]);
25         for (int i = 1; i <= n; ++i) {
26             int ff = find(a[i]), fa, fb;
27             if (i+b[i] < n) fa = find(a[i+b[i]]);
28             if(i-b[i] > 0) fb = find(a[i-b[i]]);
29             if (i+b[i] < n && fa != ff) {
30                 f[fa] = ff;
31             }
32             if (i-b[i] > 0 && fb != ff) {
33                 f[fb] = ff;
34             }
35         }
36         for (int i = 1; i <= n; ++i) {
37             if (find(i) != find(a[i])) {
38                flag = false;
39                break;
40             }
41         }
42         if (flag) puts("YES");
43         else puts("NO");
44 
45     }
46     return 0;
47 }

链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1748