Algorithmic Approach

When handling graph problems, especially those involving large datasets, an adjacency list is often preferred over an adjacency matrix to optimize memory usage, particularly when the vertex count may exceed standard limits. To determine if an undirected graph is connected, one can traverse the structure using either Depth-First Search (DFS) or Breadth-First Search (BFS). The underlying principle is that a graph is connected if and only if a single traversal iteration is sufficient to visit all nodes starting from any arbitrary vertex. The number of times the traversal function must be initiated corresponds to the number of connected components within the graph.

In a DFS implementation, a boolean array tracks visited nodes, marking a node as visited immediately upon entry. In BFS, a separate array tracks nodes that have been enqueued to prevent duplicate entries. It is crucial to mark the node as enqueued at the moment it is pushed into the queue, not when it is popped.

DFS Implementation

#include <iostream>
#include <vector>
#include <cstring>

const int MAX_VERTICES = 10005;
std::vector<int> graph[MAX_VERTICES];
bool is_visited[MAX_VERTICES];

void performDFS(int current_node) {
    is_visited[current_node] = true;
    for (int neighbor : graph[current_node]) {
        if (!is_visited[neighbor]) {
            performDFS(neighbor);
        }
    }
}

void solveGraph(int total_nodes) {
    int components = 0;
    for (int i = 1; i <= total_nodes; ++i) {
        if (!is_visited[i]) {
            performDFS(i);
            components++;
        }
    }
    std::cout << (components == 1 ? "YES" : "NO") << std::endl;
}

int main() {
    int n, m;
    while (std::cin >> n >> m && n != 0) {
        std::fill(is_visited, is_visited + n + 1, false);
        for (int i = 1; i <= n; ++i) graph[i].clear();

        for (int i = 0; i < m; ++i) {
            int u, v;
            std::cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        solveGraph(n);
    }
    return 0;
}

BFS Implementation

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

const int MAX_NODES = 10005;
std::vector<int> adj[MAX_NODES];
bool in_queue[MAX_NODES];

void runBFS(int start_node) {
    std::queue<int> q;
    q.push(start_node);
    in_queue[start_node] = true;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (int next_node : adj[curr]) {
            if (!in_queue[next_node]) {
                in_queue[next_node] = true;
                q.push(next_node);
            }
        }
    }
}

void checkConnectivity(int total_vertices) {
    int connected_components = 0;
    for (int i = 1; i <= total_vertices; ++i) {
        if (!in_queue[i]) {
            runBFS(i);
            connected_components++;
        }
    }
    std::cout << (connected_components == 1 ? "YES" : "NO") << std::endl;
}

int main() {
    int vertices, edges;
    while (std::cin >> vertices >> edges && vertices != 0) {
        for(int i=1; i<=vertices; ++i) adj[i].clear();
        std::memset(in_queue, 0, sizeof(in_queue));

        while (edges--) {
            int u, v;
            std::cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        checkConnectivity(vertices);
    }
    return 0;
}