P1017-题解（C语言代码）看一下吧！并查集算法并没有你想得那么难！

解题思路: 使用并查集算法，我是看了这个视频之后写出这道题的，授之以鱼不如授之以渔，所以把链接放在这里(并查集算法)，关键是学会算法的思想。

    
      简单来说并查集的算法就是：一开始的m个人都是单独的集合，例如{1},{2},{3},{4}.....
      当写入了1 2时，就将1 2合并到一个集合中中变成了{1,2},{3},{4}，
      再输入2 3时，就将2 3合并到一个集合中中变成了{1,2,3},{4}，
      如果我们输入2 3发现2、3都在同一个集合{1,2,3}中，就说明2 3是冗余的......依此类推即可

    注意事项：寻找某个数字的上一个节点时一定要深挖到根节点，一定要深挖到根节点，刨开他的祖坟才行！
     
参考代码: 

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>


int main() {

    //定义变量，输入数据
    int n = 0, m = 0;
    scanf("%d %d", &n, &m);
    int root[m + 1];
    root[0] = 0;
    int count = 0;//冗余数量
    for (int i = 1; i < m + 1; ++i) {
        root[i] = i;//用root[i]表示i的根节点
    }

   
    //输入一组数据就检验一次是否是冗余关系
    for (int i = 0; i < n; ++i) {
        //输入两个人的编号
        int x = 0, y = 0;
        scanf("%d %d", &x, &y);


        /*
         * 判断输入双方处于同一个集合中，是，则说明是冗余，不是，则将其合并到同一个集合中，
         * 方法就是检查输入的两个数是否具有相同的根节点即可，
         * 例如1 3和1 2的根节点都是1，当我们输入2 3时，发现root[2]=1、root[3]=1,
         * 说明2 3有共同的根节点，2 3 也就是冗余关系
         */


        //分别找出x和y的根节点，注意，一定要深挖到根节点
        while (root[x] != x) {
            x = root[x];
        }
        while (root[y] != y) {
            y = root[y];
        }

        if (x == y) {//x、y具有相同的根节点，则属于冗余
            count++;
        } else {
            /*
             * 如果两个数不冗余那就将其合并到一个集合中,
             * 例如我们输入8 9发现二者不冗余，则将root[9]的值修改为8,表示9的根节点是8
             */
            root[y] = x;
        }
    }
    printf("%d", count);
    return 0;
}