➤ Problem Link : CAM5
👉 Hint : Use DFS
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
void dfs(vector<vector<int> >&v,bool visited[100001],int i,int n)
{
vector<int>:: iterator it;
visited[i]=1;
for(it=v[i].begin();it!=v[i].end();it++)
{
if(!visited[*it])
dfs(v,visited,*it,n);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
vector<vector<int> >v(100000);
bool visited[100001];
while(t--)
{
int n,e,x,y,cnt=0;
cin>>n;
cin>>e;
for(int i=0;i<n;i++)
v[i].clear();
memset(visited,0,sizeof(visited));
while(e--)
{
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=0;i<n;i++)
{
if(!visited[i])
{
dfs(v,visited,i,n);
cnt++;
}
}
cout<<cnt<<endl;
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.