Cod sursa(job #2603096)

Utilizator hudisteanumihaelaHudisteanu Mihaela hudisteanumihaela Data 18 aprilie 2020 15:59:19
Problema Parcurgere DFS - componente conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;

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

struct nodd
{
    bool vizitat;
    vector <int> vecini;
} nod[NMAX];
int n,m,compconexe;
stack <int> stiva;

int main()
{
    int i,j,a,b,aux;
    fin>>n>>m;
    for(i=1; i<=n; i++)
    {
        fin>>a>>b;
        nod[a].vecini.push_back(b);
        nod[b].vecini.push_back(a);
    }
    for(i=1 ; i<=n ; i++)
        if(!nod[i].vizitat)
        {
            compconexe++;
            nod[i].vizitat=1;
            stiva.push(i);
            while(!stiva.empty())
            {
                aux=stiva.top();
                stiva.pop();
                for(j=0 ; j!=nod[aux].vecini.size() ; j++)
                    if(!nod[nod[aux].vecini[j]].vizitat)
                    {
                        nod[nod[aux].vecini[j]].vizitat=1;
                        stiva.push(nod[aux].vecini[j]);
                    }
            }
        }
    fout<<compconexe;
    return 0;
}