Cod sursa(job #2516504)

Utilizator JafarakKarina Jafara Jafarak Data 31 decembrie 2019 19:11:06
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f ("dfs.in");
ofstream g ("dfs.out");

const int Max=100005;

vector < int > muchii[Max];

int noduri,NrMuchii;
bool nodVizitate[Max];

void fagocitare ( int x )
{
    unsigned int i;
    nodVizitate[x]=1;
    for(i=0;i<muchii[x].size();i++)
    {
        int y;
        y=muchii[x][i];
        if(!nodVizitate[y])
            fagocitare(y);
    }
}

int nrIsles ()
{
    int i,insule=0;
    for(i=1;i<=noduri;i++)
        if(!nodVizitate[i])
        {
            insule++;
            fagocitare(i);
        }
    return insule;
}

void Read ()
{
    int i;
    f>>noduri>>NrMuchii;
    for( i=1; i <= NrMuchii; i++ )
    {
        int x, y;
        f>>x>>y;
        muchii[x].push_back(y); // goes forth
        muchii[y].push_back(x); // and back
    }
}

int main()
{
    Read();
    g<<nrIsles()<<'\n';
    return 0;
}