Cod sursa(job #1420662)

Utilizator GodstormBotarleanu Robert Godstorm Data 18 aprilie 2015 20:06:34
Problema Parcurgere DFS - componente conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>

#define NMAX 100001

enum {WHITE, BLACK};


using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

vector<list<int> > l(NMAX);
vector<bool> pass(NMAX);
int n;
int m;

inline void read() {
    fin >> n >> m;
    for(int i = 0; i <= n; i++) {
        int src, dst;
        fin >> src >> dst;
        l[src].push_back(dst);
        l[dst].push_back(src);
    }
}

void dfs(int node) {
    pass[node] = BLACK;
    for(int &n: l[node]) {
        if(pass[n] == WHITE) {
            dfs(n);
        }
    }
}

inline int findCC() {
    int cc = 0;
    for(int i = 1; i <= n; i++) {
        if(pass[i] == WHITE) {
            dfs(i);
            cc++;
        }
    }
    return cc;
}

int main()
{
    read();
    fout << findCC() << endl;
    return 0;
}