Cod sursa(job #2238486)

Utilizator Andreea_DanielaAndreea Guster Andreea_Daniela Data 5 septembrie 2018 21:32:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

void DFS(int u, const vector< vector < int> > &la, int *viz, int *tata)
{
   viz[u] = 1;
   for(unsigned i = 0; i<la[u].size(); i++)
   {
       int v = la[u][i];
       if(!viz[v])
       {
           tata[v] = u;
           DFS(v, la, viz, tata);
       }
   }
}

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

    int n, m;
    vector< vector < int> > la;

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

//    for(unsigned i=1; i<=n; i++){
//     cout << i << ": ";
//     for(unsigned j=0; j<la[i].size(); j++)
//        cout << la[i][j] << " ";
//     cout << endl;
//     }

    int *viz = new int[n+1];
    int *tata = new int[n+1];
    int nr_comp_conexe = 0;

    for(int i=1; i<=n; i++)
        viz[i] = tata[i] = 0;

    for(int i=1; i<=n; i++)
    {
        if(!viz[i]){
            nr_comp_conexe ++;
            DFS(i, la, viz, tata);
        }
    }
    fout << nr_comp_conexe;
    fout.close();

    return 0;
}