You are given an unweighted, undirected graph. Write a
program to check if it's a tree topology.
Input. The first line contains two integers n and m – number of nodes and number of edges in the graph (0 < n ≤ 10000, 0 ≤ m ≤ 20000). Next m lines contain m edges of that graph. Each line contains a pair (u, v)
means there is an edge between node u and node v (1 ≤ u, v
≤ n).
Output. Print YES if the given graph is a tree, otherwise
print NO.
Sample Input
3 2
1 2
2 3
Sample Output
YES
дерево
Запустим поиск в глубину из любой (например, первой)
вершины и подсчитаем количество с
вершин, через которые он прошел. Граф является деревом, если он связный и без
циклов. Для этого необходимо, чтобы число его ребер было на единицу меньше
числа вершин, а значение с равнялось n.
Реализация алгоритма
#include <cstdio>
#include <cstring>
#include <vector>
using namespace
std;
int i, j, n, m, a, b, c, Edges;
vector<vector<int>
> g;
vector<int> used;
void dfs(int
v)
{
int i, to;
used[v] = 1; c++;
for(i = 0; i < g[v].size(); i++)
{
to = g[v][i];
if (!used[to]) dfs(to);
}
}
int main(void)
{
scanf("%d %d",&n,&m); Edges = c = 0;
g.assign(n+1,vector<int>());
used.assign(n+1,0);
for(i = 0; i < m; i++)
{
scanf("%d %d",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
Edges++;
}
dfs(1);
if ((Edges == n - 1) && (c == n)) printf("YES\n"); else
printf("NO\n");
}