Cod sursa(job #2797476)

Utilizator IoanaLiviaPopescu15Ioana Livia IoanaLiviaPopescu15 Data 9 noiembrie 2021 22:56:30
Problema Parcurgere DFS - componente conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;

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

int N, M;

class Graph
{
public:
    map<int, bool> visited;
    map<int, list<int> > adj;

    void addEdge(int v, int w);
    void DFS(int v);

};

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
    adj[w].push_back(v);
}

void Graph::DFS(int v)
{
    visited[v] = 1;
   // cout << v << " ";


    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (visited[*i] != 1){
            DFS(*i);
        }
}

int main()
{
    Graph g;

    fin>>N>>M;
    int cnt = 0;
    for(int i = 0; i < M; ++i){
        int n1,n2;
        fin>>n1>>n2;
        g.addEdge(n1,n2);
    }

    for(int i = 1; i <= N; ++i)
    {
        if(!g.visited[i]){
             cnt++;
             g.DFS(i);
        }
    }

    fout<<cnt;
    return 0;
}