Cod sursa(job #2820503)

Utilizator oporanu.alexAlex Oporanu oporanu.alex Data 20 decembrie 2021 15:24:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.56 kb
#include <bits/stdc++.h>
using namespace std;
#define directed true
#define undirected false
#define weighted true
#define unweighted false

/*class Edge{
    int i, j, cost;
    Edge(int _i, int _j, int _cost) : i(_i), j(_j), cost(_cost){}

    friend bool operator<(const Edge& e1, const Edge& e2) {
          return e1.cost < e2.cost;
    }
    // util in ordonarea dupa cost
};
// o structura de tip muchie, utila in problema APM cand, aplicand algoritmul lui Kruskall
// avem nevoie sa sortam muchiile crescator dupa cost
*/

class Graph {
public:
    int V;
    int E;
    bool dir;
    bool wgt;
    Graph(bool, bool);
    // constructorul care contine doar informatii de tipul
    // 'graful este orientat/neorientat si are/n-are costuri pe muchii'
    void build(int, int, vector<vector<pair<int, int>>>);
    vector<vector<pair<int, int>>> adj;
    // lista de adiacenta a nodului 'n' e formata din perechi de tipul
    // {vecin, cost}, unde cost = costul muchiei {n, vecin}.
    // daca graful n-are costuri pe muchii cost = 0;
    void DFSUtil(int, vector<bool>&, vector<int>&);
    vector<int> DFS(int, vector<bool>&);
    int cc(int);

};

Graph::Graph(bool _directed, bool _weighted) : dir(_directed), wgt(_weighted) {
}

void Graph::build(int _V, int _E, vector<vector<pair<int, int>>> _adj) {
    V = _V;
    E = _E;
    adj = _adj;
}

void Graph::DFSUtil(int v, vector<bool>& vis, vector<int>& island){
    for(auto i : adj[v]){
        int ngb = i.first;
        if(!(vis[ngb])) {
            island.push_back(ngb);
            vis[ngb] = true;
            DFSUtil(ngb, vis, island);
        }
    }
}
vector<int> Graph::DFS(int src, vector<bool>& vis) {
    vector<int> island;
    DFSUtil(src, vis, island);
    return island;
}

int Graph::cc(int src) {
    int nrIslands = 0;
    vector<bool> vis;
    vis.resize(V + 1, false);
    for(int i = 1; i <= V; ++i) {
        if(!vis[i]){
            ++nrIslands;
            DFS(i, vis);
        }
    }
    return nrIslands;
}

int main()
{
    // problema dfs pe pe infoarena
    // https://www.infoarena.ro/problema/dfs
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    int v, e;
    fin >> v >> e;
    vector<vector<pair<int, int>>> adj;
    adj.resize(v + 1);
    Graph g(undirected, unweighted);
    for(int i = 1; i <= e; ++i) {
        int src, dst;
        fin >> src >> dst;
        adj[src].push_back(make_pair(dst, 0));
        adj[dst].push_back(make_pair(src, 0));
    }
    g.build(v, e, adj);
    fout << g.cc(1);
    return 0;
}