Cod sursa(job #2301894)

Utilizator Maghiar_Octavian_FMI_UVTMaghiar Octavian Maghiar_Octavian_FMI_UVT Data 13 decembrie 2018 17:14:42
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <list>
using namespace std;
class Graph{
    int n;
    list<int> *edges;
public:
    Graph(int n){
        this->n=n;
        this->edges = new list<int>[n];

    };
    void addEdge(int x,int y){
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    void DFS(int s,bool visited[]){
        visited[s]=true;
        for(list<int>::iterator i = edges[s].begin();i!=edges[s].end();i++){
            if(!visited[*i]){
                DFS(*i,visited);
            }
        }
    }
};
int main()
{
    ifstream f("dfs.in");
    ofstream g("dfs.out");
    int m,n,x,y,k(0);
    f>>n>>m;
    Graph *g = new Graph(n);
    while(m--){
        f>>x>>y;
        g->addEdge(x,y);
    }
    bool *visited = new bool[n];
    for (int i = 0; i < n; i++)
        visited[i] = false;
    for (int i = 0; i < n; i++){
        if(!visited[i]){
            ++k;
            g->DFS(i,visited);
    }}
    g<<k;
    f.close();
    g.close();
    return 0;
}