Cod sursa(job #2636999)

Utilizator andreic06Andrei Calota andreic06 Data 20 iulie 2020 21:30:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
/// componente conexe

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
const int N = 1e5;
const int M = 2e5;

vector <int> edges[N+1];
int visited[N+1];

void dfs ( int start_node ){
    visited[start_node] = 1;
    printf ( "%d\n", start_node );
    for ( int i = 0; i < (int)edges[start_node].size (); i ++ )
       if ( visited[edges[start_node][i]] == 0 )
         dfs ( edges[start_node][i] );
}

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

int main()
{
   int n, m;
   fin >> n >> m;

   for ( int i = 1; i <= m; i ++ ) {
       int x, y;
       fin >> x >> y;
       edges[x].push_back ( y );
       edges[y].push_back ( x );
   }


   int res = 0;
   for ( int i = 1; i <= n; i ++ ) {
      if ( visited[i] == 0 )
        dfs ( i ), res ++;
   }

   fout << res;

    return 0;
}