Cod sursa(job #2230801)

Utilizator HumikoPostu Alexandru Humiko Data 11 august 2018 15:49:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define MMAX 200005

using namespace std;

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

int n, m, answer;
int f[NMAX];

vector <int> graph[NMAX];

int dfs(int node)
{
    f[node] = 1;

    for ( auto x:graph[node])
        if ( f[x] == 0 )
            dfs(x);

    return 1;
}

int main()
{
    fin>>n>>m;
    for ( int i = 1; i <= m; ++i )
    {
        int first_Node, second_Node;

        fin>>first_Node>>second_Node;
        graph[first_Node].push_back(second_Node);
        graph[second_Node].push_back(first_Node);
    }

    for ( int i = 1; i <= n; ++i )
        if ( f[i] == 0 )
            answer += dfs(i);

    fout<<answer<<'\n';
}