Graphs/Number_of_provinces.cpp at main · SparshGarg999/Graphs · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
https://practice.geeksforgeeks.org/problems/number-of-provinces/1
//Number of Provinces
//approach-1 DFS
/*
TC - O(V+E) + O(N)
SC - O(N) + O(2*E)
*/
void dfsNumberofProvinces(int node,vector<int>&vis,vector<int>adj[]){
    vis[node]=1;
    for(auto it:adj[node]){
        if(!vis[it])
            dfsNumberofProvinces(it,vis,adj);
    }
}
    int numProvinces(vector<vector<int>> adj, int V) {
        // code here
        /*DisjointSet st(V);
        for(int i=0;i<V;i++){+
            for(int j =0;j<V;j++){
                if(adj[i][j] == 1) st.SizeByUnion(i,j);
            }
        }
        int cnt=0;
        for(int i = 0; i< V;i++)if(st.parent[i] == i) cnt++;return cnt;*/

        vector<int>adjL[V];
        for(int i=0;i<V;i++){
            for(int j = 0;j<V;j++){
                if(adj[i][j]){
                    adjL[i].push_back(j);
                    adjL[j].push_back(i);
                }
            }
        }
        int cnt= 0;
        vector<int>vis(V,0);
        for(int i=0;i<V;i++){
            if(!vis[i]){
                cnt++;
                dfsNumberofProvinces(i,vis,adjL);
            }
        }
        return cnt;
    //approach -2
    /*
    TC - O(V+E) + O(N)
    Sc - O(2*E) + O(N)
    */
        queue<int> q;
        vector<int> vis(V,0);
        int cnt=0;

        for(int i=0;i<V;i++){
            if(!vis[i]){
                vis[i] =1;
                q.push(i);
                cnt++;
            while(!q.empty()){
                int node = q.front();q.pop();
                for(auto it:adjL[node]) {
                    if(!vis[it]){
                        vis[it]=1;
                        q.push(it);
                    }
                }
            }
        }
    }
    return cnt;
}