本文主要是介绍【并查集】HDU 1325 Is It A Tree?，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
HDU 1325 Is It A Tree?
就是判断能不能成为一棵树。空树也是树。
根据连通性，根节点个数，入度出度等。
#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;int fa[100005], vis[100005];
int in[100005];int get_f(int x)
{if(x != fa[x]) fa[x] = get_f(fa[x]);return fa[x];
}int main()
{bool is_lt = false;int cnt = 0, cas = 0, flag = 0;int maxx = -0x3f3f3f3f;for(int i = 0; i < 100005; i++)fa[i] = i, vis[i] = in[i] = 0;int a, b;while(scanf("%d%d", &a, &b) != EOF){if(a == -1 && b == -1) break;if(a == 0 && b == 0){int temp = 0;for(int i = 0; i <= maxx; i++){if(vis[i]){if(fa[i] == i) temp++;if(in[i] == 0) cnt++;}}if(temp <= 1) is_lt = true;cas ++;printf("Case %d ", cas);if(is_lt && cnt == 1 && flag == 0) puts("is a tree.");else if(temp == 0 && cnt == 0) puts("is a tree.");else puts("is not a tree.");is_lt = false, cnt = 0;for(int i = 0; i < 100005; i++)fa[i] = i, vis[i] = in[i] = 0;maxx = -0x3f3f3f3f;flag = 0;continue;}vis[a] = vis[b] = 1;maxx = max(maxx, a);maxx = max(maxx, b);in[b]++;a = get_f(a), b = get_f(b);if(a == b) flag = 1;fa[a] = b;}return 0;
}
这篇关于【并查集】HDU 1325 Is It A Tree?的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
