Cod sursa(job #314495)

Utilizator mihaionlyMihai Jiplea mihaionly Data 11 mai 2009 22:33:59
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
using namespace std;
#define dim 100001
long nr,n,m;
unsigned a[dim][100],viz[dim];
void read()
 {
 int x,y,i;
 ifstream f("dfs.in");
 f>>n>>m;
 for(i=1;i<=m;i++)
  {
  f>>x>>y;
  a[x][++a[x][0]]=y;
  a[y][++a[y][0]]=x;
  }
 }
int neviz()
 {
 for(int i=1;i<=n;i++)
  if(viz[i]==0)
   return i;
 return 0;
 }
int mai_e()
 {
 for(int i=1;i<=n;i++)
  if(viz[i]==0)
   return 1;
 return 0;
 }
void dfs(int x)
 {
 viz[x]=1;
 for(int i=1;i<=a[x][a[x][0]];i++)
  if(viz[a[x][i]]==0)
   dfs(a[x][i]);
 }
void solve()
 {
 do
  {
  dfs(neviz());
  nr++;
  }while(mai_e());
 }
void show()
 {
 ofstream g("dfs.out");
 g<<nr;
 }
int main()
 {
 read();
 solve();
 show();
 return 0;
 }