判斷一個圖是不是樹

問題描述

給一個以0 0結尾的整數對列表，除0 0外的每兩個整數表示一條連接了這兩個節點的邊。假設節點編號不超過100000大于0。你只要判斷由這些節點和邊構成的圖是不是樹。是輸出YES，不是輸出NO。

輸入樣例1

6 8  5 3  5 2  6 4 5 6  0 0

輸出樣例1

YES

輸入樣例2

8 1  7 3  6 2  8 9  7 5 7 4  7 8  7 6  0 0

輸出樣例2

YES

輸入樣例3

3 8  6 8  6 4 5 3  5 6  5 2  0 0

輸出樣例3

NO

輸入樣例4

1 2 3 4 0 0

輸出樣例4

NO

輸入樣例5

空樹也是樹

0 0

輸出樣例5

YES

c++代碼

#include<bits/stdc++.h>
#include<stdio.h>using namespace std;int a, b, cont = 0;
int arr[100001];
bool key = true;
unordered_set<int> st;int myfind(int x) {int root = x;while(root != arr[root]) root = arr[root];int i = x, j;while(i != root) {j = arr[i];arr[i] = root;i = j;}return root;
}void mymerge(int x, int y) {x = myfind(x), y = myfind(y);if (x != y) arr[y] = arr[x];
}int main() {for (int i = 1; i <= 100000; i++) arr[i] = i;while(true) {scanf("%d %d", &a, &b);if (a == 0 && b == 0) {if (cont == 0) {printf("YES\n");return 0;}if (key && st.size() != cont + 1) key = false;if (key) {int root = -1;for (int x : st) {int k = myfind(x);if (root == -1) root = k;if (k != root) {key = false;break;}}}if (key) printf("YES\n");else printf("NO\n");break;}else {cont++;if (st.find(a) == st.end()) st.insert(a);if (st.find(b) == st.end()) st.insert(b);if (key) {int x = myfind(a), y = myfind(b);if (x == y) key = false;else mymerge(a, b);}}}return 0;
}

算法解析

滿足下面三個條件的圖是樹

1、不存在環。

2、所有點都是互相連通的。

3、點數=邊數 + 1。

判斷環

用并查集，給每個點一個初始的編號，并初始化所有節點的父親為本身。每新加入一條邊就把邊相連的兩個集合合并到一起，如果邊相連的集合原本就是同一個，說明已經成環，不是生成樹。

int x = myfind(a), y = myfind(b);
if (x == y) key = false; //邊相連的集合原本就是同一個，說明已經成環，不是生成樹。
else mymerge(a, b); //否則合并一下

判斷節點數和邊數的關系

把點存在一個unordered_set里面就行，因為不能存重復的，邊用一個cont就可以存

cont++;
if (st.find(a) == st.end()) st.insert(a);
if (st.find(b) == st.end()) st.insert(b);
......
if (key && st.size() != cont + 1) key = false;

判斷連通性

如果是連通的，根據我們之前的合并操作，每一個節點應該都屬于同一個集合，如果不是，則不是樹。

int root = -1;
for (int x : st) {int k = myfind(x);if (root == -1) root = k;if (k != root) {key = false;break;}
}