jayati

Number of Operations to Make Network Connected

Mar 22nd, 2023
222
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.92 KB | None | 0 0
  1. class Solution {
  2. public:
  3.  
  4.   void dfs(vector<int> adj[], vector<bool> &visited, int src)
  5.     {
  6.         visited[src] = true;
  7.         for(int i : adj[src]){
  8.             if(!visited[i]){
  9.                 dfs(adj, visited, i);
  10.             }
  11.         }
  12.     }
  13.     int makeConnected(int n, vector<vector<int>>& connections) {
  14.          if(connections.size()<n-1)
  15.         {
  16.             return -1;
  17.         }
  18.         vector<int> gr[n];
  19.         for(auto cable : connections){
  20.             gr[cable[0]].push_back(cable[1]);
  21.             gr[cable[1]].push_back(cable[0]);
  22.         }
  23.        
  24.             int ans=0;
  25.             vector<bool> visited(n,0);
  26.             for(int i=0;i<n;i++)
  27.             {
  28.                 if(!visited[i])
  29.                 {
  30.                     dfs(gr,visited,i);
  31.                      ans++;
  32.                 }
  33.                
  34.             }
  35.             return ans-1;
  36.        
  37.        
  38.     }
  39. };
Advertisement
Add Comment
Please, Sign In to add comment