Cod sursa(job #3243760)

Utilizator edidanciuDanciu Eduard Florin edidanciu Data 20 septembrie 2024 19:56:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

void dfs(vector<vector<int>> &graph, vector<bool> &visited,int node)
{
    visited[node]=true;
    for(int neighbor:graph[node])
    {
        if(!visited[neighbor])
        {
            dfs(graph,visited,neighbor);
        }
    }
}
int main()
{
    int n,m;
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");

    fin >> n >> m;

    vector<vector<int>> graph(n+1,vector<int> ());
    vector<bool> visited(n+1,false);

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

    int cnt=0;

    for(int i=1;i<=n;i++)
    {
        if(!visited[i])
        {
            cnt++;
            dfs(graph,visited,i);
        }
    }
    fout << cnt;
    return 0;
}