Cod sursa(job #281763)

Utilizator MirceampMuresan Mircea Paul Mirceamp Data 15 martie 2009 21:23:22
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int pus[100],a[1000][1000],n,m;
void read(){
     int i,x,y;
     fin>>n>>m;
     for(i = 1; i <= m; i++){
           fin>>x>>y;
           a[x][y] = 1;
           a[y][x] = 1;
     }
fin.close();
}
void df(int k){
     int i;
     pus[k] = 1;
     for(i = 1; i <= n; i++)
     if(a[k][i] == 1 && !pus[i])
     df(i);
}
int main(){
    int i,cul;
    cul = 0;
    read();
    for(i = 1; i <= n; i++)
          {
               if(pus[i] == 0){
               df(i);
               cul++;
               }
          }
    fout<<cul<<"\n";
fout.close();
return 0;
}