Cod sursa(job #2030677)

Utilizator eduardandrei20Nechifor Eduard Andrei eduardandrei20 Data 1 octombrie 2017 22:53:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <stdio.h>
#include <fstream>
#define NN 100001
using namespace std;
int viz[NN],n;
struct nod{
int info;
nod *next;
};
nod *L[NN];
void adaug(int x,int y)
{
    //adaug pe x la lista lui y
    nod *k=new nod;
    k->info=y;
    k->next=L[x];
    L[x]=k;



}

void citire(){

freopen("dfs.in","r",stdin);
scanf("%d",&n);

int m;
scanf("%d",&m);
for(int i=1; i<=m ;++i)
{
    int x,y;
    scanf("%d%d",&x,&y);
    adaug(x,y);
    adaug(y,x);
}

}

void bfs(int x){

viz[x]=true;
nod *aux;
for(aux=L[x]; aux; aux=aux->next)
    if(!viz[aux->info])bfs(aux->info);



}
int main()
{int componente=0;
citire();
for(int i=1; i<=n ;++i)
if(!viz[i]){
    bfs(i);
    ++componente;


}
freopen("dfs.out","w",stdout);
printf("%d",componente);
    return 0;
}