Connected Components

    1#include <bits/stdc++.h>
    2 
    3using namespace std;
    4 
    5vector<vector<int>> adj, components;
    6vector<bool> visited;
    7 
    8void dfs(int u, vector<int>& comp){
    9    visited[u] = true;
    10    comp.push_back(u + 1); // 1 based index
    11    for(int v : adj[u]){
    12        if(!visited[v]){
    13            dfs(v, comp);
    14        }
    15    }
    16}
    17int main(){
    18    ios::sync_with_stdio(0);
    19    cin.tie(0);
    20    int n;
    21    cin >> n;
    22    adj.resize(n); visited.resize(n);
    23 
    24    for(int i = 0; i < n; i++){
    25        for(int j = 0; j < n; j++){
    26            int c;
    27            cin >> c;
    28            if(c == 1){
    29                adj[i].push_back(j); // add edge from node i to j
    30            }
    31        }
    32    }
    33    for(int i = 0; i < n; i++){
    34        if(!visited[i]){
    35            vector<int> comp;
    36            dfs(i, comp);
    37            sort(comp.begin(), comp.end());
    38            components.push_back(comp);
    39        }
    40    }
    41    sort(components.begin(), components.end());
    42    for(auto &comp : components){
    43        for(int node : comp){
    44            cout << node << " ";
    45        }
    46        cout << '\n';
    47    }
    48    return 0;
    49}