Cod sursa(job #1772144)

Utilizator danielNiculaeDaniel Niculae danielNiculae Data 6 octombrie 2016 15:38:22
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include "fstream"
#include "vector"
#include "queue"

using namespace std;

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

const int INF = 1000000005;
const int NMAX = 100005;


vector<int> graph[NMAX];
queue<int> q;
bool used[NMAX];
int components = 0;

void dfs(int node) {
    used[node] = true;
    for(int i = 0 ; i < graph[node].size() ; i++) {
        if(!used[graph[node][i]]) {
            dfs(graph[node][i]);
        }
    }
}

int main() {
    int N, M;
    fin >> N >> M;
    for(int i = 1 ; i <= M ; i++) {
        int x, y;
        fin >> x >> y;

        graph[x].push_back(y);
    }

    for(int i = 1 ; i <= N ; i++ ) {
        if(!used[i]) {
            components++;
            dfs(i);
        }
    }

    fout << components;


    fin.close();
    fout.close();
    return 0;
}