Cod sursa(job #1828031)

Utilizator maribMarilena Bescuca marib Data 12 decembrie 2016 18:26:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#define DIM 100005
#define MUCHII 500005
#define INF 0x3f3f3f3f
using namespace std;

vector < pair<int, int> > v;

int n, m, a, b;

class graph {

public:
    vector <int> edges[DIM];
    int nodes;
    graph(vector< pair<int, int> > v, int x);
    int conex();
};

graph::graph(vector < pair<int, int> > v, int x){
    for(int i = 0; i < v.size(); ++i){
        edges[v[i].first].push_back(v[i].second);
        edges[v[i].second].push_back(v[i].first);
        //graf neorientat
    }
    nodes = x;
}

int graph::conex(){
    int node, neigh;
    bool vis[DIM];
    memset(vis, false, DIM);
    queue <int> q;
    int result = 0;
    for(int i = 1; i <= nodes; ++i){
        if(!vis[i]){
            q.push(i);
            result++;
            while(!q.empty()){
                node = q.front();
                q.pop();
                for(int j = 0; j < edges[node].size(); ++j){
                    neigh = edges[node][j];
                    if(!vis[neigh]){
                        q.push(neigh);
                        vis[neigh] = true;
                    }
                }
            }
        }
    }
    return result;
}

int main()
{
    ifstream in("dfs.in");
    ofstream out("dfs.out");
    in>>n>>m;
    for(int i = 1; i <= m; ++i){
        in>>a>>b;
        v.push_back(make_pair(a, b));
    }
    graph g (v, n);
    out<<g.conex();
    in.close();
    out.close();
    return 0;
}