clusters_from_adjacent_matrix.cpp

#include <iostream>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

void bfs(int start, vector<vector<int>>& adj, vector<bool>& visited, vector<int>& cluster) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    cluster.push_back(start);

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

        for (int i = 0; i < adj[node].size(); i++) {
            if (adj[node][i] == 1 && !visited[i]) {
                visited[i] = true;
                q.push(i);
                cluster.push_back(i);
            }
        }
    }
}

vector<vector<int>> findClusters(vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    vector<vector<int>> clusters;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            vector<int> cluster;
            bfs(i, adj, visited, cluster);
            clusters.push_back(cluster);
        }
    }

    return clusters;
}

int main() {
    int n = 9;
    
    vector<vector<int>> adj(n, vector<int>(n, 0));
    vector<pair<int, int>> edges;
    edges.emplace_back(0, 3);
    edges.emplace_back(1, 8);
    edges.emplace_back(1, 7);
    edges.emplace_back(2, 6);
    edges.emplace_back(2, 7);
    edges.emplace_back(4, 6);
    edges.emplace_back(5, 6);
    edges.emplace_back(7, 8);
    for (const auto &[i0, i1]: edges) {
        adj[i0][i1] =  1;
        adj[i1][i0] =  1;
    }
    vector<vector<int>> clusters = findClusters(adj);
    cout << "The clusters in the graph are:\n";
    for (auto& cluster : clusters) {
        cout << "{ ";
        for (int node : cluster) {
            cout << node << " ";
        }
        cout << "}\n";
    }

    return 0;
}