Cod sursa(job #1847366)

Utilizator abccnuCamelia Zalum abccnu Data 14 ianuarie 2017 16:09:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int NMAX=100003;

int n , m, sol;

bool vis[NMAX];

vector<int>lista[NMAX];

void dfs( int x )
{
    vis[x] = 1;
    for ( int i = 0; i < lista[x].size(); ++ i )
    {
        if ( vis[lista[x][i]] == 0 )
        {
            dfs(lista[x][i]);
        }
    }
}

int main()
{
    int i, j, x, y;
    fin>>n>>m;
    for (i=1; i<=m; ++i)
    {
        fin>>x>>y;
        lista[x].push_back(y);
        lista[y].push_back(x);
    }
for ( i = 1; i <= n; ++ i )
    {
        if ( vis[i] == 0 )
        {
            ++ sol;
            dfs(i);
        }
    }
    fout<<sol;
    return 0;
}