Cod sursa(job #1382365)

Utilizator mariusadamMarius Adam mariusadam Data 8 martie 2015 21:52:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <vector>
#define n_max 100002
using namespace std;

ifstream r("dfs.in");
ofstream w("dfs.out");

vector <long> g[n_max];
int viz[n_max];
long n,m,nrc;

void read() {
    long i,j,k;
    r>>n>>m;
    for (k=0; k<m; k++) {
        r>>i>>j;
        g[i].push_back(j);
        g[j].push_back(i);
    }
}

void df(long nod) {
    viz[nod]=1;
    for (vector <long>::iterator it=g[nod].begin(); it!=g[nod].end(); it++)
            if (viz[*it]==0)
                df(*it);
}

int main() {
    long i;
    read();
    for (i=1; i<=n; i++)
        if (viz[i]==0) {
            df(i);
            nrc++;
    }
    w<<nrc<<"\n";
    r.close();
    w.close();
}