Cod sursa(job #316255)

Utilizator mihaionlyMihai Jiplea mihaionly Data 18 mai 2009 22:18:50
Problema Parcurgere DFS - componente conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <vector>
using namespace std;
#define dim 100005
ifstream f("dfs.in");
ofstream g("dfs.out");
vector<long> v[dim];
bool viz[dim];
long n,m,x;
void read()
 {
 f>>n>>m;
 long x,y,i;
 for(i=1;i<=n;i++)
  v[i].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]++;
  }
 }
int mai_merge()
 {
 int i;
 for(i=1;i<=n;i++)
  if(viz[i]==false)
   {
   x=i;
   return 1;
   }
 return 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();
 do
  {
  solve(x);
  nr++;
  }while(mai_merge());
 g<<nr;
 return 0;
 }