Cod sursa(job #2085515)

Utilizator lulian23Tiganescu Iulian lulian23 Data 10 decembrie 2017 12:15:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>
#define nmax 123456

using namespace std;

vector < int > v[ nmax ];
int n, m, nr;
bool viz[ nmax ];

void dfs(int nod){

        viz[ nod ] = 1;

        for (auto it : v[ nod ])
            if (!viz[ it ])
              dfs(it);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    ifstream cin("dfs.in");
    ofstream cout("dfs.out");

    cin >> n >> m;

    for (int i = 0, x, y; i < m; i++){
        cin >> x >> y;
        v[ x ].push_back( y );
        v[ y ].push_back( x );
    }

    for (int i = 1; i <= n; i++)
        if (viz[ i ] == 0){
            ++nr;
            dfs( i );
        }

    cout << nr;
}