1st

 avatar
Naveen
plain_text
25 days ago
1.8 kB
1
Indexable
Never
// TC: O(V+E)

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

vector<list<int>>graph; // Graph representation
unordered_set<int>visited; // Set to track visited nodes
vector<vector<int>>result; // Vector to store all paths

int v; // number of vertices

// add edge function
void addEdge(int src, int dest, bool biDir=true){

    graph[src].push_back(dest); // list me push_back kiya hai
    if(biDir){
        graph[dest].push_back(src); // agar bi directional hai to dest me bhi push
    }
}

void dfs(int node, unordered_set<int>&visited){

    visited.insert(node);
    for(auto neighbour: graph[node]){
        if(!visited.count(neighbour)){

            dfs(neighbour,visited);
        }
    }
}

int connectedComponent(){

    int result = 0;
    unordered_set<int>visited; // visited is passed by reference

    for(int i=0; i<v; i++){ // go to every node

        if(visited.count(i) == 0){
            result++; // jitni baar dfs(not taking about resursive calls in dfs) hoga utne connected component
            dfs(i,visited);
        }
    }

    return result;
}

int main(){

    // graph input 
    //cout<<"Enter the number of vertices"<<endl;
    cin>>v;
    graph.resize(v, list<int>());

    int e;
    //cout<<"Enter the number of edges"<<endl;
    cin>>e;
    visited.clear();

    while(e--){

        int s,d;
        //cout<<"Enter source vertex"<<endl;
        //cin>>s;

        //cout<<"Enter destination vertex"<<endl;
        //cin>>d;

        cin>>s>>d;

        addEdge(s,d); // for directed graph just add false in agrument

    }

    cout<<"Number of connected graph: "<<connectedComponent()<<endl;

    
    return 0;
}
Leave a Comment