Cod sursa(job #2280678)

Utilizator andonis1616And Cuz andonis1616 Data 10 noiembrie 2018 23:30:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#define NMAX 200005
using namespace std;
ifstream in ("dfs.in");
ofstream out ("dfs.out");

int n,m;
bool vizitat[NMAX];
int answer;

struct Nod
{
    int curent;
    Nod* urm;
};

typedef Nod* PNod;

PNod muchii[NMAX];
PNod final_muchii[NMAX];

void adauga(int i,int j)
{
    if(muchii[i]==NULL){
        muchii[i]=new Nod;
        muchii[i]->urm=NULL;
        muchii[i]->curent=j;
        final_muchii[i]=muchii[i];
    }
    else{
        PNod aux=new Nod;
        aux->curent=j;
        final_muchii[i]->urm=aux;
        aux->urm=NULL;
        final_muchii[i]=aux;
    }
}

void DFS(int x)
{
    vizitat[x]=true;
    int nod_curent;
    if(muchii[x]!=NULL){
        for(PNod i=muchii[x];i!=NULL;i=i->urm){
            nod_curent=i->curent;
            if(!vizitat[nod_curent]){
                DFS(nod_curent);
            }
        }
    }
}

int main()
{
    int i,x,y;
    in>>n>>m;
    for(i=1;i<=m;i++){
        in>>x>>y;
        adauga(x,y);
        adauga(y,x);
    }
    for(i=1;i<=n;i++){
        if(!vizitat[i]){
            answer++;
            DFS(i);
        }
    }
    out<<answer;
    return 0;
}