#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
public:
// Конструктор класу Graph
Graph(int n) : num_vertices(n) {
// Ініціалізація списку суміжності
adj.resize(n);
}
// Додавання ребра в граф
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
// Перевірка зв'язності графа
bool isConnected() {
// Масив відвіданих вершин
vector<bool> visited(num_vertices, false);
// Очередь для BFS
queue<int> q;
// Додаємо першу вершину до черги
q.push(0);
// Позначаємо першу вершину як відвідану
visited[0] = true;
while (!q.empty()) {
// Беремо першу вершину з очереді
int u = q.front();
q.pop();
// Перебираємо всі суміжні з u вершини
for (int v : adj[u]) {
// Якщо вершина v ще не була відвідана, додаємо її до черги
// і позначаємо як відвідану
if (!visited[v]) {
q.push(v);
visited[v] = true;
}
}
}
// Перевіряємо, чи всі вершини були відвідані
for (int i = 0; i < num_vertices; i++) {
if (!visited[i]) {
return false;
}
}
return true;
}
private:
// Кількість вершин в графі
int num_vertices;
// Список суміжності для графа
vector<vector<int>> adj;
};
int main() {
// Відкриваємо файл з графом
ifstream input_file("graph.txt");
// Зчитуємо кількість вершин у графі
int num_vertices;
input_file >> num_vertices;
cout << "The numder of vertices: " << num_vertices << endl;
// Створюємо граф з num_vertices вершинами
Graph g(num_vertices);
// Зчитуємо ребра з файлу та додаємо їх до графа
int u, v;
while (input_file >> u >> v) {
g.addEdge(u, v);
}
// Перевіряємо зв'язність графа та виводимо результат
if (g.isConnected()) {
cout << "Graph is connected" << endl;
} else {
cout << "Graph isn't connected" << endl;
}
return 0;
}
