Connected Component

component.cpp

#include<iostream>
#include<vector>
using namespace std;

class Graph{
    int V;
    vector<int> *l;
public:
    Graph(int v){
        V = v;
        l = new vector<int>[V];
    }

    void addEdge(int x, int y, bool undir = true){
        l[x].push_back(y);
        if(undir)
            l[y].push_back(x);
    }

    void dfs(int src, vector<bool> &visted){
        visted[src] = true;
        for(auto node:l[src]){
            if(!visted[node]){
                dfs(node, visted);
            }
        }
    }
};

int main(){
    Graph g(8);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(3, 4);
    g.addEdge(5, 6);
    g.addEdge(6, 7);
    vector<bool> visted(8, false);
    int c=0;
    for(int i=0; i<8; i++){
        if(!visted[i]){
            g.dfs(i, visted);
            c++;
        }
    }
    cout<<c<<endl;
}