Created
July 12, 2020 15:31
-
-
Save Irene-123/46d9881ac26250c9a18d13c089bafa71 to your computer and use it in GitHub Desktop.
help the Prayatna pr team-SPOJ C++ Solution
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
``` | |
#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