Cod sursa(job #2682279)

Utilizator andrei.florea0405Florea Andrei-Bogdan andrei.florea0405 Data 8 decembrie 2020 13:17:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;

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

vi G[100010];
vector<bool> visited(100010);


void dfs(int node) {
    visited[node] = 1;
    for (auto &it : G[node]) {
        if (!visited[it]) {
            dfs(it);
        }
     }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    fin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;
        G[x].pb(y);
        G[y].pb(x);
    }
    
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            count++;
            dfs(i);
        }
    }

    fout << count << "\n";

    return 0;
}