Cod sursa(job #2242250)

Utilizator mihaicivMihai Vlad mihaiciv Data 18 septembrie 2018 10:16:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#define nmax 100100
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n, m, vis[nmax];
struct nod {
    int info;
    nod *urm;
}*a[nmax];
void Adauga(int n1, int n2) {
    if (a[n1] == NULL) {
        a[n1] = new nod();
        a[n1]->info = n2;
        a[n1]->urm = NULL;
    } else {
        nod *aux = a[n1];
        while (aux->urm != NULL) {
            aux = aux->urm;
        }
        aux->urm = new nod();
        aux = aux->urm;
        aux->info = n2;
        aux->urm = NULL;
    }
}
void citire() {
    f >> n >> m;
    int x, y;
    for (int i = 1;i <= m;i ++) {
        f >> x >> y;
        Adauga(x, y);
        Adauga(y ,x);
    }
}
void DFS(int x) {
    vis[x] = 1;
    nod * aux = a[x];
    while (aux != NULL) {
        int vCurr = aux->info;
        if (vis[vCurr] == 0) {
            DFS(vCurr);
        }
        aux = aux->urm;
    }
}
void rez() {
    int Answer = 0;
    for (int i = 1;i <= n;i ++) {
        if (vis[i] == 0 ) {
            //cout << i << " ";
            Answer ++;
            DFS(i);
        }
    }
    g << Answer;
}
void afiseaza(int x) {
    nod * aux = a[x];
    while (aux != NULL) {
        cout << aux->info << " ";
        aux = aux->urm;
    }
}
int main() {
    citire();
    //afiseaza(1);
    rez();
    return 0;
}