Cod sursa(job #3266491)

Utilizator sLinXDinca Robert sLinX Data 8 ianuarie 2025 21:25:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
//  --------------------------------------------------------
// BFS

//#include <iostream>
//#include <fstream>
//
//#include <vector>
//#include <queue>
//
//using namespace std;
//
//
//ifstream f("bfs.in");
//ofstream g("bfs.out");
//vector<vector<int>> lista;
//queue<int> q;
//vector<int> distanta;
//
//int main()
//{
//    int n,m,s;
//    f >> n >> m >> s;
//    int x,y ;
//    lista.resize(n+1);
//    distanta.resize(n+1,-1);
//    q.push(s);
//    distanta[s] = 0;
//    while(f >> x >> y)
//    {
//        lista[x].push_back(y);
//    }
//    while(!q.empty())
//    {
//        int curr = q.front();
//        q.pop();
//        for(auto vecin : lista[curr]){
//            if(distanta[vecin] == -1){
//                distanta[vecin] = distanta[curr] + 1;
//                q.push(vecin);
//            }
//        }
//    }
//
//    for(int i = 1; i<=n ;i++)
//        g << distanta[i] << ' ' ;
//
//    return 0;
//}

// -----------------------------------------------------------------------------
// DFS

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int n,m;

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

vector<vector<int>> lista;
vector<bool> verif;

void dfs(int nod)
{
    if(verif[nod])return;
    verif[nod] = true;
    for(auto vecin: lista[nod])
    {
        dfs(vecin);
    }
}

int main()
{
    int x,y;
    f >> n >> m;
    lista.resize(n+1,{});
    verif.resize(n+1, false);
    while(f >> x >> y)
    {
        lista[x].push_back(y);
        lista[y].push_back(x);
    }

    int nrComp = 0;
    for(int i = 1; i<=n; i++)
    {
        if(!verif[i])
        {
            nrComp++;
            dfs(i);
        }
    }

    g << nrComp;

    f.close();
    g.close();

    return 0;
}