Cod sursa(job #2790223)

Utilizator dascalu_maraDascalu Mara Elena dascalu_mara Data 28 octombrie 2021 16:57:42
Problema Parcurgere DFS - componente conexe Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
//
//  main.cpp
//  Algoritmi aplicati pe grafuri
//
//  Created by Mara Dascalu on 27/10/2021.
//

#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#include <map>
#include <list>

using namespace std;

ifstream input("dfs.in");
ofstream output("dfs.out");
 class Graph
{
    int nodes, edges;
    map<int, list<int>> adj;
   
public:
    
    map<int, bool> visited;
    void set_no_nodes(int n) {nodes = n;}
    int get_no_nodes() {return nodes;}
    void set_no_edges(int n) {edges = n;}
    int get_no_edges() {return edges;}
    void addEdge (int a, int b)
    {
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    void DFS(int node)
    {
        visited[node] = 1;
        //output<<node<<" ";
        
        list<int> :: iterator iter;
        for (iter = adj[node].begin(); iter != adj[node].end(); iter++)
            if( !visited[*iter])
                DFS(*iter);
    }
//    void afis_adj(int node){
//        list<int> :: iterator i;
//        for(i = adj[node].begin(); i != adj[node].end(); i++)
//            output<<*i<<" ";
//    }
}g;
int main(int argc, const char * argv[]) {
    int no_nodes, no_edges, n1, n2, cc=0;
    input>>no_nodes>>no_edges;
    for (int i = 0; i < no_edges; i++)
    {
        input>>n1>>n2;
        g.addEdge(n1, n2);
    }
    for (int i = 1; i <= no_nodes; i++)
        if (!g.visited[i])
        {
            cc++;
            g.DFS(i);
        }
    output<<cc<<" ";
}