Cod sursa(job #2091259)

Utilizator radu20000Radu Harabagiu radu20000 Data 19 decembrie 2017 13:45:53
Problema Parcurgere DFS - componente conexe Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>

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

const int NMAX=100000;
int n,m,start;
bool uz[NMAX];
vector<int> G[NMAX];

void citire();
void afisare();
void dfs(int x);
void descompunere();

int main() {
citire();
descompunere();
return 0;
}

void citire(){
int i,x,y;
fin>>n>>m;
for(i=0;i<m;i++){
    fin>>x>>y;
    G[x].push_back(y);
    G[y].push_back(x);

}

}

void afisare(){
    int i,x;
    for(x=1;x<=n;x++){
        for(i=0;i<G[x].size();i++)
            fout<<G[x][i]<<' ';
        fout<<'\n';
    }
}

void dfs(int x){

int i;
uz[x]=1;
for(i=0;i<G[x].size();i++)
    if(uz[G[x][i]]==0)
        dfs(G[x][i]);
}




void descompunere(){
int i,nr=0;
for(i=1;i<=n;i++){
    if(!uz[i]){
            nr++;
        dfs(i);
    }
}
fout<<nr;
}