# Untitled

unknown
c_cpp
2 years ago
1.5 kB
2
Indexable
Never
```#include <bits/stdc++.h>
using namespace std;

// Stores the parent of each vertex
int parent[1000000];

// Function to find the topmost
// parent of vertex a
int root(int a)
{
// If current vertex is
// the topmost vertex
if (a == parent[a]) {
return a;
}

// Otherwise, set topmost vertex of
// its parent as its topmost vertex
return parent[a] = root(parent[a]);
}

// Function to connect the component
// having vertex a with the component
// having vertex b
void connect(int a, int b)
{
// Connect edges
a = root(a);
b = root(b);

if (a != b) {
parent[b] = a;
}
}

// Function to find unique top most parents
void connectedComponents(int n)
{
set<int> s;

// Traverse all vertices
for (int i = 0; i < n; i++) {

// Insert all topmost
// vertices obtained
s.insert(root(parent[i]));
}

// Print count of connected components
cout << s.size() << '\n';
}

{

// Setting parent to itself
for (int i = 0; i <= N; i++) {
parent[i] = i;
}

// Traverse all edges
for (int i = 0; i < edges.size(); i++) {
connect(edges[i][0], edges[i][1]);
}

connectedComponents(N);
}

// Driver Code
int main()
{
// Given N
int N = 8;

// Given edges
vector<vector<int> > edges = {
{ 1, 0 }, { 0, 2 }, { 5, 3 }, { 3, 4 }, { 6, 7 }
};

// Function call