HDOJ1272——判断无向图的连通性

题目描述

给定一个无向图，判断该图任意两点之间是否有且仅有一条路径可以相通

题目思路

• 并查集可以维护是否属于同一组这一信息
• 本题中如果两个点属于同一组，则说明它们连通
• 对于输入的两个点，如果它们不在同一个组，将它们合并到同一个组
  如果它们在同一个组，说明它们之间已经有一条路径可以相通，这时又添加一条路径，所以不符合题目要求

需要注意的地方

• 除了判断输入的两个点是否已经在一个组，还需要判断整个图是否连通。判断的方法是当点对输入完之后，判断输入的点所在组的根节点是否都一样，如果都一样，说明连通。

AC代码

#include "stdio.h"
int p[100010];//p[i] is the root of i
int r[100010];//r[i] is the depth of the tree that i is in
int f[100010];//f[i] = 1 when f is one of the input

//initial the sets
void init(){
    for(int i = 1; i < 100010; i++){
        p[i] = i;
        r[i] = 0;
        f[i] = 0;
    }
}
//Find(x) return the root of x
int Find(int x){
    if(x == p[x]) return x;
    else return p[x] = Find(p[x]);
}

//Union(x, y) union the sets of x and y
void Union(int x, int y){
    int xRoot = Find(x);
    int yRoot = Find(y);

    if(xRoot == yRoot) return;
    if(r[xRoot] < r[yRoot]) p[xRoot] = yRoot;
    else if(r[xRoot] > r[yRoot]) p[yRoot] = xRoot;
    else{
        p[yRoot] = xRoot;
        r[xRoot]++;
    }
}

bool sameRoot(int x, int y){
    return Find(x) == Find(y);
}

int main(){
    int x, y;
    init();
    int flag = 1;//flag = 1 when satisfies the requires
    while(1){
        scanf("%d %d", &x, &y);
        if(x == -1 && y == -1) return 0;
        if(x == 0 && y == 0){
            int r = 0;//root
            //judge whether the design is connected
            for(int i = 1; i < 100010; i++){
                if(f[i] == 1){
                    //if i is one of the input
                    //get the root
                    if(r == 0) r = Find(i);
                    else {
                        if(r != Find(i)) flag = 0;
                    }
                }
            }
            if(flag) printf("Yes\n");
            else printf("No\n");
            init();
            flag = 1;
            continue;
        }
        f[x] = 1;//x is one of the input
        f[y] = 1;//y is one of the input
        if(!sameRoot(x, y)) Union(x, y);
        else{
            flag = 0;
        }
    }
}

收获

• 并查集可以判断一个图是否连通
• 并查集可以判断一个图中两个点是否有且仅有一条路径相通