Cod sursa(job #2797459)

Utilizator IoanaLiviaPopescu15Ioana Livia IoanaLiviaPopescu15 Data 9 noiembrie 2021 22:08:15
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 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);

    int k = 0;
    int noduri_in_componente_conexe = 0;
    void mark_unvisited(int poz);
    int conexe();
};

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

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


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

void Graph::mark_unvisited(int poz)
{
    visited[poz] = false;
}

int Graph::conexe()
{
    return k;
}



int main()
{
    Graph g;

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

    int nr_comp_conexe = 0;
    for(int i = 1; i <= N; ++i)
    {
        g.DFS(i);
        if(nr_comp_conexe == g.conexe())
        {
            g.mark_unvisited(i);
        }
        else
        {
            nr_comp_conexe = g.conexe();
        }
    }

    //cout<<nr_comp_conexe;
    int total_noduri_in_comp_conexe = g.noduri_in_componente_conexe + nr_comp_conexe;
   // cout<<total_noduri_in_comp_conexe;

    fout<<N - total_noduri_in_comp_conexe + nr_comp_conexe;

    return 0;
}