Cod sursa(job #280419)

Utilizator SoRReLLIftode Bogdan Marius SoRReLL Data 13 martie 2009 13:06:49
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<iostream.h>
#include<fstream.h>

int a[1005][1005]={0},n,viz[1005]={0},k=0;
long m;

void citire()
{
     fstream in("dfs.in",ios::in);
     in>>n>>m;
     for(long i=1;i<=m;i++)
              {
                           int x,y;
                           in>>x>>y;
                           a[x][y]=1;
                           a[y][x]=1;
              }
     in.close();
}

void dfs(int x)
{
     viz[x]=1;
     for(int i=1;i<=n;i++)
             if(!viz[i]&&a[x][i])
                                 dfs(i);
}

void scrie()
{
     fstream out("dfs.out",ios::out);
     out<<k;
     out.close();
}

int main()
{
    citire();
    for(int i=1;i<=n;i++)
            if(!viz[i])
                       {
                                     k++;
                                     dfs(i);
                       }
    scrie();
    return 0;
}