【九度OJ】题目1109：连通图 解题报告

标签（空格分隔）： 九度OJ

---

原题地址：http://ac.jobdu.com/problem.php?pid=1109

题目描述：

给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。

输入：

每组数据的第一行是两个整数 n 和 m（0<=n<=1000）。 n 表示图的顶点数目，m 表示图中边的数目。 如果 n 为 0 表示输入结束。 随后有 m 行数据，每行有两个值 x 和 y（0<x, y <=n）， 表示顶点 x 和 y 相连，顶点的编号从 1 开始计算。 输入不保证这些边是否重复。

输出：

对于每组输入数据，如果所有顶点都是连通的，输出”YES”，否则输出”NO”。

样例输入：

4 3 1 2 2 3 3 2 3 2 1 2 2 3 0 0

样例输出：

NO YES

Ways

同样是并查集的问题，试想，我们如何确定这些点与点是否相连接？根据前面题目的结论，我们可以在每个节点都保存着它的根节点是谁，如果一群点拥有相同的根节点就说明是有可以相连接的。

那么，如何判断所有的顶点是否为连通图呢？我们知道用Tree[x]的办法，根节点的Tree[x]的值是-1，其他节点的Tree[x]是根节点的值，遍历所有节点，找出为-1的节点的个数，如果不是1，说明至少两个根节点，那么也就说明不是连通图。

题目中的两个例子：

x1234root2334Tree[x]23-1-1

输出NO

x123root233Tree[x]23-1

输出YES

#include<stdio.h> int Tree[1002]; int findRoot(int x) { if (Tree[x] == -1) { return x; } else { int temp = findRoot(Tree[x]); Tree[x] = temp; return temp; } } int main() { int m, n; while (scanf("%d%d", &n, &m) != EOF && n != 0) { for (int i = 1; i <= n; i++) { Tree[i] = -1; } while (m-- != 0) { int a, b; scanf("%d%d", &a, &b); int aRoot = findRoot(a); int bRoot = findRoot(b); if (aRoot != bRoot) { Tree[aRoot] = bRoot; } } int count = 0; for (int i = 1; i <= n; i++) { if (Tree[i] == -1) { count++; } } if (count == 1) { printf("YES\n"); } else { printf("NO\n"); } } return 0; }

Date

2017 年 3 月 10 日