Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- void dfs(vector<int> adj[], vector<bool> &visited, int src)
- {
- visited[src] = true;
- for(int i : adj[src]){
- if(!visited[i]){
- dfs(adj, visited, i);
- }
- }
- }
- int makeConnected(int n, vector<vector<int>>& connections) {
- if(connections.size()<n-1)
- {
- return -1;
- }
- vector<int> gr[n];
- for(auto cable : connections){
- gr[cable[0]].push_back(cable[1]);
- gr[cable[1]].push_back(cable[0]);
- }
- int ans=0;
- vector<bool> visited(n,0);
- for(int i=0;i<n;i++)
- {
- if(!visited[i])
- {
- dfs(gr,visited,i);
- ans++;
- }
- }
- return ans-1;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment