hihocoder1322 : 树结构判定(161周)

题目链接

思路：

无向图中判断是不是一棵树。

• 并查集判断。判断是不是只有一个连通分量。并且该联通分量中没有环。没有环的判定很简单就是看边的数目和顶点数目，如果边数大于等于顶点数则存在环。
• 也可以用dfs来做。

ac代码：

// hiho1322_161week.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#include<iostream>

#include<cstdio>

#include<string>

#include<algorithm>

#include<queue>

#include<vector>

#include<cstring>

#include<unordered_map>

using namespace std;

int pre[505];

int find(int x)

{

	return pre[x] == x ? x : find(pre[x]);

}

void merge(int x, int y)

{

	int xx = find(x);

	int yy = find(y);

	if (xx == yy) return;

	pre[yy] = xx;

}

int main()

{

	int t, n, m;

	cin >> t;

	while (t--)

	{

		cin >> n >> m;

		for (int i = 1; i <= n; i++)

		{

			pre[i] = i;

		}

		int x, y;

		for (int i = 0; i < m; i++)

		{

			cin >> x >> y;

			merge(x, y);

		}

		int count = 0;

		for (int i = 1; i <= n; i++)

		{

			if (pre[i] == i)

			{

				count++;

			}

			if (count > 1) break;

		}

		if (count == 1 && m < n) cout << "YES" << endl;

		else cout << "NO" << endl;

	}

    return 0;

}