Cod sursa(job #1771941)

Utilizator AetheryonStefan Bereghici Aetheryon Data 6 octombrie 2016 11:03:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 100013;

class Graph {
    private :
        int nodes;
        int edges;
        vector <int> AdjList[Nmax];
        bool used[Nmax];

        void dfs (int node){
            used[node] = 1;
            for (int i=0;i<this->AdjList[node].size();++i){
                if (!used[this->AdjList[node][i]]){
                    dfs(this->AdjList[node][i]);
                }
            }
        }

    public :
        Graph (int n,int m){
            this->nodes = n;
            this->edges = m;
            for (int i=1;i<=n;++i){
                used[i] = 0;
                AdjList[i].clear();
            }
        }

        void addEdge(int from,int to){
            this->AdjList[from].push_back(to);
        }

        int getConnectedComponents(){
            int cnt = 0;
            for (int i=1;i<=this->nodes;++i){
                if (!used[i]){
                    ++cnt;
                    this->dfs(i);
                }
            }
            return cnt;
        }
};

int main(){
    ifstream cin("dfs.in");
    ofstream cout("dfs.out");
    int n,m,from,to;
    cin>>n>>m;
    Graph *graph = new Graph(n,m);
    for (int i=0;i<m;++i){
        cin>>from>>to;
        graph->addEdge(from,to);
        graph->addEdge(to,from);
    }
    cout<<graph->getConnectedComponents();
    return 0;
}