Задача. Проверить, является ли заданный неориентированный граф связным, то есть что из любой вершины можно по рёбрам этого графа попасть в любую другую.
Входные данные
В первой строке заданы количество вершин [latex]n[/latex] и ребер [latex]m[/latex] в графе соответственно [latex](1 \leq n \leq 100, 1 \leq m \leq 10000)[/latex]. Каждая из следующих m строк содержит по два числа [latex]u_i[/latex] и [latex]v_i[/latex] [latex](1 \leq u_i, v_i \leq n);[/latex] каждая такая строка означает, что в графе существует ребро между вершинами [latex]u_i[/latex] и [latex]v_i[/latex].
Выходные данные
Выведите «YES», если граф является связным и «NO» в противном случае.
Тесты
Тесты, взятые с e-olymp.com
| Test | Input | Output |
| 1 | 3 2 1 2 3 2 |
YES |
| 2 | 3 1 1 3 |
NO |
Мои тесты
| Test | Input | Output |
| 1 | 4 2 1 2 3 4 |
NO |
| 2 | 4 5 1 2 2 1 2 4 2 4 4 2 |
NO |
| 3 | 5 4 1 2 5 1 3 5 4 3 |
YES |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <bits/stdc++.h> using namespace std; #define in_range(x,y,z) for(int x=y; x<z; x++) int main() { int m,n; cin >> n >> m; vector < vector<int> > g(n); // граф int s=0; // начальная вершина in_range(i,0,m) // считывание графа { int u,v; cin >> u >> v; g[u-1].push_back(v-1); g[v-1].push_back(u-1); } queue<int> q; // очередь с вершинами, которые мы рассматриваем на данном этапе q.push (s); vector<bool> used (n); // логический массив, указывающий, посещена ли вершина used[s] = true; while (!q.empty()) // пока мы не обойдем все вершины, которые можно достигнуть из данной { int v = q.front(); q.pop(); // достаем из головы очереди одну вершину for (size_t i=0; i<g[v].size(); ++i) //просмотрим все ребра, исходящие из данной вершины { int to = g[v][i]; if (!used[to]) // если текущая вершина еще не была посещена { used[to] = true; //отмечаем, что мы ее посетили q.push (to); // помещаем в очередь } } } vector<bool>::iterator it; it = find (used.begin(), used.end(), false); // проверяем, остались ли еще непосещенные вершины if (it == used.end()) cout << "YES"; // если все вершины посещены, то граф связный else cout << "NO"; return 0; } |
Алгоритм
Чтобы установить, является ли граф связным, я использовала удобный для этого алгоритм поиска в ширину. Он заключается в следующем: начиная с какой-то вершины, мы поочередно просматриваем все вершины, соседние с ней. Каждую посещенную вершину мы помечаем маркером. Затем повторяем этот процесс для каждой из соседних вершин, и так далее. Поиск будет продолжаться, пока мы не обойдем все вершины, которые можно достигнуть из данной. Если после этого в графе осталась хотя бы одна не помеченная вершина, значит из нее нельзя попасть в помеченные, то есть граф не является связным. При этом неважно, с какой вершины мы будем начинать поиск, ведь нам нужно установить сам факт, связный граф или нет.
Засчитанное решение на сайте e-olymp.com
Молодец. Это гораздо быстрее, чем то решение, которое когда-то отправлял я.