Cod sursa(job #321979)

Utilizator mihaionlyMihai Jiplea mihaionly Data 7 iunie 2009 20:57:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>  
#include <vector>  
#include <algorithm>  
using namespace std;  
#define dim 100005  
ifstream f("dfs.in");  
ofstream g("dfs.out");  
vector<long> v[dim];  
vector<bool> viz;  
long n,m,x;  
void read()  
 {  
 f>>n>>m;  
 long x,y,i;  
 viz.push_back(1);  
 for(i=1;i<=n;i++)  
  {  
  v[i].push_back(0);  
  viz.push_back(0);  
  }  
 for(i=1;i<=m;i++)  
  {  
  f>>x>>y;  
  v[x].push_back(y);  
  v[y].push_back(x);  
  v[x][0]++;  
  v[y][0]++;  
  }  
 }  
void solve(long x)  
 {  
 viz[x]=1;  
 long i;  
 for(i=1;i<=v[x][0];i++)  
  {  
  if(viz[v[x][i]]==0)  
   solve(v[x][i]);  
  }  
 }  
int main()  
 {  
 x=1;  
 int nr=0;  
 read();  
 for(int i=1;i<=n;i++)
  if(!viz[i])
   {
   solve(i);
   nr++;
   }
 g<<nr;  
 return 0;  
 }