Cod sursa(job #2424116)

Utilizator Madalina_CirsteaCIRSTEA IONELA-MADALINA Madalina_Cirstea Data 22 mai 2019 17:09:42
Problema Parcurgere DFS - componente conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <vector>

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

void DFS(int nod,vector<int>&viz,vector<vector<int>>&G)
{
    viz[nod]=1;

    for (auto vecin:G[nod])
        if (!viz[vecin])
            DFS(vecin,viz,G);
}

int main()
{
    int n,m,x,y;

    f>>n>>m;

    vector<vector<int>> G(n+1);
    vector<int>viz(n+1,0);

    for (int i=0; i<m; i++)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    int ok=0;//presupunem ca nu am gasit toate comp conexe
    int sursa=1,nr=0;

    while(!ok)
    {
        ok=1;
        DFS(sursa,viz,G);
        nr++;
        for (int i=1; i<=n; i++)
            if (viz[i]==0)
            {
                ok=0;
                sursa=i;
                break;
            }
    }

    g<<nr;

}