HDU 1272 小希的迷宫

https://vjudge.net/problem/HDU-1272

学数据结构时没认真学，这题加深了我对图和树的认识，所以记录一下

题目要求图中的任意两点有且仅有一条路径相连，我们第一个直觉就是图中不能存在环 =>不存在环的情况下，将图连通只需要n-1条边 => 但不能只去数边数来写这题，因为有可能边数是n-1，但他把某些点给孤立了，然后剩下的点通过这些边形成了回路 => 于是我们就有了思路 ： 符合小希的设计的条件是：只有n-1条边，并且这些顶点不存在回路。

不存在回路用并查集去判断就行了

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int maxn = 1e5+50;
int fa[maxn];
bool flag;
void ini()
{
	for(int i = 0; i < maxn; i++) fa[i] = i;
}
int getf(int x)
{
	return fa[x] = fa[x] == x ? x : getf(fa[x]); 
}
void merge(int x,int y)
{
	int fx = getf(x),fy = getf(y);
	if(fx != fy){
		fa[fy] = x;
	}
	else flag = true;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int a,b;
	while(scanf("%d%d",&a,&b)){
		if(a == -1 && b == -1) break;
		if(a == 0 && b == 0){
			printf("Yes\n");
			continue;
		}
		set<int> S;
		int num = 1;
		ini();
		flag = false;
		merge(a,b);
		S.insert(a);S.insert(b);
		if(flag) printf("No\n");
		while(scanf("%d%d",&a,&b) && a && b){
			num++;
			merge(a,b);
			S.insert(a);S.insert(b);
		}
		if(flag || num != S.size()-1) printf("No\n");
		else printf("Yes\n");
	}
	return 0;
}

总结：（我也不知道对不对，如果有错大家一定要指出来啊）

1.图与树的关系：不存在孤立点的情况下，树是不含回路的图

2.将一个图连通只需要n-1条边，如果少了连不成，如果多了存在回路

3.判断无向图是否连通可以用并查集，最起码并查集比较好写

HDU 1272 小希的迷宫

原文：https://www.cnblogs.com/Beic233/p/13181108.html