Cod sursa(job #642521)

Utilizator danieladDianu Daniela danielad Data 1 decembrie 2011 16:31:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#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;
}