Cod sursa(job #2425246)

Utilizator alex_galatanAlex Galatan alex_galatan Data 24 mai 2019 17:24:20
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

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

struct nod{
    int nr, ordin, vizitat;
    vector <int> legaturi;
};

vector<nod> noduri;
int n;

int parcurge(int i)
{
    int k;
    noduri[i].vizitat = 1;
    for (k = 0; k < noduri[i].legaturi.size(); k++)
        if (noduri[noduri[i].legaturi[k] - 1].vizitat == 0)
            parcurge(noduri[i].legaturi[k] - 1);
}

int main()
{
    int m, i, a, b;

    f>>n>>m;
    for (i = 0; i  < n; i++)
    {
        nod nou;
        nou.nr = i + 1;
        nou.ordin = 0;
        nou.vizitat = 0;
        noduri.push_back(nou);
    }

    for (i = 0; i < m; i++)
    {
        f>>a>>b;
        //noduri[b-1].ordin++;
        noduri[b-1].legaturi.push_back(a);
        noduri[a-1].legaturi.push_back(b);
    }

    int con = 0;
    for(i = 0; i < n; i++)
        if (noduri[i].vizitat == 0)
        {
            con++;
            parcurge(i);
        }

    g<<con;

    return 0;
}