并查集——poj1308（并查集延伸）

题意：给你一系列形如u v的点对（u v代表一条由u指向v的有向边），请问由给你的点构成的图是不是一棵树？

树的特征：①每个节点（除了根结点）只有一个入度；②只有一个根结点。

题解：用并查集合并点，对于一条边，如果连接的两点已经在同一并查集内，则可以直接判否。合并时按边的方向记录点的入度，如果某个点入度大于1也就是某个点有多个父亲节点，则说明不是树。合并时顺便记录合并总次数，最后合并点数-1次则是树。

代码：

#include <stdio.h>

#include <memory.h>

const int MAX_SIZE = 105;

int parent[MAX_SIZE];

bool flag[MAX_SIZE];

void make_set(){  //初始化

	for(int x = 1; x < MAX_SIZE; x ++){

		parent[x] = x;

		flag[x] = false;

	}

}

int find_set(int x){   //寻找根节点，带路径压缩

	if(x != parent[x])

		parent[x] = find_set(parent[x]);

	return parent[x];

}

void union_set(int x, int y){  //合并

	x = find_set(x);

	y = find_set(y);

	if(x == y) return;

	parent[y] = x;

}

bool single_root(int n){   //判断是不是只有一个根，条件(1)

	int i = 1;

	while (i <= n && !flag[i]){

		++i;

	}

	int root = find_set(i);

	while (i <= n){

		if (flag[i] && find_set(i) != root){

			return false;

		}

		++i;

	}

	return true;

}

int main(){

	int x, y;

	bool is_tree = true;

	int range = 0;

	int idx = 1;

	make_set();

	while (scanf("%d %d", &x, &y) != EOF){

		if (x < 0 || y < 0){

			break;

		}

		if (x == 0 || y == 0){

			if (is_tree && single_root(range)){

				printf("Case %d is a tree.\n", idx++);

			}

			else{

				printf("Case %d is not a tree.\n", idx++);

			}

			is_tree = true;

			range = 0;

			make_set();

			continue;

		}

		if (!is_tree){

			continue;

		}

		range = x > range ? x : range;

		range = y > range ? y : range;

		flag[x] = flag[y] = true;

		if (find_set(x) == find_set(y)){  //如果两者属于一个集合（也就是有共同祖先），并且两者还有父子关系，那么无法形成树，条件2

			is_tree = false;

		}

		union_set(x, y);

	}

	return 0;

}

巴特西

并查集——poj1308（并查集延伸）

最新文章

热门文章