Cod sursa(job #2424565)

Utilizator mihaidanielmihai daniel mihaidaniel Data 23 mai 2019 12:03:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

int v[100001];
vector <int> mat[100001];

void DFS (int x)
{
    vector <int> :: iterator vi = mat[x].begin(), vf =mat[x].end();
    while (vi != vf) {
        if (v[*vi] == 0) {
            v[*vi] = 1;
            DFS (*vi);
        }
        ++vi;
    }
}

int main()
{
    //ifstream in ("date.in");/*
    ifstream in ("dfs.in");
    ofstream out ("dfs.out");//*/
    int n, m, i, x, y, nr = 0;
    in >> n >> m;
    for (i = 0; i < m; ++i) {
        in >> x >> y;
        mat[x].push_back (y);
        mat[y].push_back (x);
    }

    for (i = 1; i <= n; ++i) {
        if (v[i] == 0) {
            ++nr;
            v[i] = 1;
            DFS(i);
        }
    }

    out << nr;
    return 0;
}