Cod sursa(job #147550)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 3 martie 2008 10:02:25
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream.h>
#include <fstream.h>

#define IN "dfs.in"
#define OUT "dfs.out"
#define maxx 100003

struct date
{
 long x;
 long y;
}m[maxx];
long n,mm;
long sol;      

long s[maxx];
long v[maxx];

ifstream fin(IN);
ofstream fout(OUT);

void citire();
long alg();

int main()
{
 citire();
  fin.close();
  
 memset(v,-1,sizeof(v));
 sol=alg();
 
 fout<<sol<<endl;
 
 fout.close();
 
return 0;
}

void citire()
{
 long i;
     
 fin>>n>>mm;
 
 for(i=1;i<=n;i++)
 {
  fin>>m[i].x;
  fin>>m[i].y;
 }
}      

long alg()
{
 long i;
 long c;
     
 for(i=1;i<=n;i++)
  s[i]=i;
  
 for(i=1;i<=mm;i++)
  if(s[m[i].x]!=s[m[i].y])
   s[m[i].y]=s[m[i].x];
   
 for(i=1;i<=n;i++)       
  if(v[s[i]])
  {
   v[s[i]]++;
   sol=sol+1;
  }
return sol;
}