Cod sursa(job #1316378)

Utilizator LucacelRazvanLucacel Razvan LucacelRazvan Data 13 ianuarie 2015 19:37:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#define DMax 100001
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector<int> Lista[DMax];
int N,M;
bool vazut[DMax];
void Citire()
{
    int X,Y,i;
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {
        fin>>X>>Y;
        Lista[X].push_back(Y);
        Lista[Y].push_back(X);
    }
    fin.close();
}
void Afis_lista()
{
    int i,j;
    for(i=1;i<=N;i++){
        cout<<i<<": ";
        for(j=0;j<Lista[i].size();j++) cout<<Lista[i][j]<<" ";
        cout<<'\n';
    }
    fout.close();
}

void DFS(int v){
    int i;
    vazut[v]=true;
    for(i=0;i<Lista[v].size();i++)
        if(!vazut[Lista[v][i]]) DFS(Lista[v][i]);
}

int main()
{
    int i,cmp=0;
    Citire();
    //Afis_lista();
    for(i=1;i<=N;i++) if(!vazut[i]){cmp++; DFS(i);}
    fout<<cmp;
    return 0;
}