Skip to content

Instantly share code, notes, and snippets.

@Irene-123
Created July 12, 2020 15:31
Show Gist options
  • Save Irene-123/46d9881ac26250c9a18d13c089bafa71 to your computer and use it in GitHub Desktop.
Save Irene-123/46d9881ac26250c9a18d13c089bafa71 to your computer and use it in GitHub Desktop.
help the Prayatna pr team-SPOJ C++ Solution
```
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
int state[1000004];
vector<int>v[100005];
void bfs(int source){
queue<int>q;
q.push(source);
state[source]=1;
while(!q.empty()){
int current=q.front();
q.pop();
for (int i=0;i<v[current].size();i++){
if (state[v[current][i]]==0){
q.push(v[current][i]);
state[v[current][i]]=1;
}
}
}
}
int main()
{
int n,m;
cout<<"Enter the number of friends and number of relations:\n";
cin>>n>>m;
int x,y,ans;
memset(v,0,sizeof(v));
memset(state,0,sizeof(state));
for (int i=0;i<m;i++){ //input the relations
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
int count=0;
for (int i=0;i<n;i++){
if (state[i]==0){ //if a node is not visited then
bfs(i); //call the bfs function
count++;
}
}
cout<<count<<endl;
return 0;
}
```
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment