Cod sursa(job #1169244)

Utilizator robert_fanrRobert Banu robert_fanr Data 10 aprilie 2014 19:11:55
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");

int n, nr, contor;
bool m[1000][1000], vizitat[1000];

void citire() {
    in >> n >> nr;
    int i, a, b;
    for (i=1; i<=nr; i++) {
        in >> a >> b;
        m[a][b] = true;
        m[b][a] = true;
    }
}

void dfs(int i) {
    vizitat[i] = true;
    int j;
    for (j=1; j<=n; j++)
        if (m[i][j])
            if (!vizitat[j])
                dfs(j);
}

void start() {
    int i;
    for (i=1; i<=n; i++)
        if (!vizitat[i]) {
            contor++;
            dfs(i);
        }
}

int main()
{
    citire();
    start();
    out << contor;
    return 0;
}