Pagini recente » Cod sursa (job #24346) | Cod sursa (job #2070177) | Cod sursa (job #2317020) | Cod sursa (job #1702631) | Cod sursa (job #642521)
Cod sursa(job #642521)
#include<fstream>
#include<vector>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
vector <int> a[100001];
int n,m,b,c[100001],viz[100001];
void citire(int &n)
{int x,y;
f>>n>>m;
for(int i=1;i<=m;i++){
f>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
}
void BFS(int s){
int p,u,v;
c[1]=s;
viz[s]=1;
p=u=1;
while(p<=u){
v=c[p];
for(int i=0;i<a[v].size();i++)
if(viz[a[v][i]]==0){
u++;
c[u]=a[v][i];
viz[a[v][i]]=1;
}
p++;
}
}
int main(){
citire(n);
int nr=0;
for(int i=1;i<=n;i++)
viz[i]=0;
for(int i=1;i<=n;i++)
if(viz[i]==0){
nr++;
BFS(i);
}
g<<nr;
return 0;
}