You are viewing a single comment's thread. Return to all comments →
C++ solution. Note the condition when both keys give the same parent using the find function. In that case, we have to return without doing anything.
#include <bits/stdc++.h> #include<limits.h> using namespace std; /* * Complete the componentsInGraph function below. */ int find(vector<int>&parent, int a){ if(parent[a]!=a) parent[a] = find(parent, parent[a]); return parent[a]; } void merge(vector<int>&parent, vector<int>& rank, vector<int>& saz, int a, int b){ int i_id = find(parent,a); int j_id = find(parent, b); if(i_id == j_id) return; if(rank[i_id] < rank[j_id]){ parent[i_id] = j_id; saz[j_id] = saz[j_id] + saz[i_id]; } else{ parent[j_id] = i_id; saz[i_id] = saz[i_id] + saz[j_id]; if(rank[i_id]==rank[j_id]) rank[i_id]++; } } vector<int> componentsInGraph(vector<vector<int>> gb) { int N = gb.size(); vector<int> res; vector<int> parent,rank,saz; parent.resize(2*N+1); rank.resize(2*N+1); saz.resize(2*N+1); parent[0]=-1; rank[0]=-1; saz[0]=-1; for(int i=1; i<2*N+1; i++){ parent[i] = i; rank[i] = 0; saz[i] = 1; } for (int gb_row_itr = 0; gb_row_itr < N; gb_row_itr++) { int a= gb[gb_row_itr][0]; int b= gb[gb_row_itr][1]; //cout << a << " " << b << endl; merge(parent, rank, saz, a, b); } int max=INT_MIN; int min=INT_MAX; for(int i=1; i<2*N+1; i++){ int i_p = find(parent,i); max=std::max(max,saz[i_p]); if(saz[i_p]!=1){ min=std::min(min,saz[i_p]); //cout << i_p << " " << size[i_p] << " "; //cout << '\n'; } } res.push_back(min); res.push_back(max); return res; } int main() { ofstream fout(getenv("OUTPUT_PATH")); int n; cin >> n; cin.ignore(numeric_limits<streamsize>::max(), '\n'); vector<vector<int>> gb(n); for (int gb_row_itr = 0; gb_row_itr < n; gb_row_itr++) { gb[gb_row_itr].resize(2); for (int gb_column_itr = 0; gb_column_itr < 2; gb_column_itr++) { cin >> gb[gb_row_itr][gb_column_itr]; } cin.ignore(numeric_limits<streamsize>::max(), '\n'); } vector<int> result = componentsInGraph(gb); for(int i=0; i<result.size(); i++){ fout << result[i] << " "; } fout << "\n"; fout.close(); return 0; }
Components in a graph
You are viewing a single comment's thread. Return to all comments →
C++ solution. Note the condition when both keys give the same parent using the find function. In that case, we have to return without doing anything.