Cod sursa(job #2793153)

Utilizator dascalu_maraDascalu Mara Elena dascalu_mara Data 3 noiembrie 2021 08:55:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.4 kb
//
//  main.cpp
//  Algoritmi aplicati pe grafuri
//
//  Created by Mara Dascalu on 27/10/2021.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <bits/stdc++.h>
#include <map>
#include <list>
#include <set>

using namespace std;

ifstream input("dfs.in");
ofstream output("dfs.out");

class Graph
{
    int nodes, edges;
    vector<int> adj[100010] ;
    bool visited[100010] = {0};
    int cc = 0;
    int cost[100010] = {0};
    queue<int> queue_bfs;
    int level[100010] = {0};
    int low_level[100010] = {0};
    stack<pair<int, int>> component_node;
    vector<int> vec_scc[100010];
    queue<int> queue_ts; //coada in care vom adauga doar nodurile care au gradul interior 0
    int indegree[100010] ; //vectorul care retine gradul interior al fiecarui nod
    vector<int> degree_seq; //vectorul care contine gradele unui posibil graf

public:

    vector<int> bcc[100010]; //vectorul care stocheaza componentele biconexe
    int current = 0;

   void set_no_nodes(int n) {nodes = n;}
   int get_no_nodes() {return nodes;}
   void set_no_edges(int n) {edges = n;}
   int get_no_edges() {return edges;}

   void addEdge_dg ()
   {
       int no_nodes, no_edges;
       input>>no_nodes>>no_edges;
       set_no_nodes(no_nodes);

       int node1, node2;

       for(int i = 0 ; i < no_edges; i++)
       {
           input>>node1>>node2;
           adj[node1].push_back(node2);
       }


   }

   void addEdge_ug ()
   {
       int no_nodes, no_edges;
       input>>no_nodes>>no_edges;
       set_no_nodes(no_nodes);

       int node1, node2;

       for(int i = 0 ; i < no_edges; i++)
       {
           input>>node1>>node2;
           adj[node1].push_back(node2);
           adj[node2].push_back(node1);
       }
   }


   void DFS(int node)
   {
       visited[node] = 1;
//       output<<node<<" ";

       for (int i = 0; i < adj[node].size(); i++)
           if( !visited[adj[node][i]])
               DFS(adj[node][i]);
   }

//   void afis_adj(int node){
//       for (int i = 0; i < adj[node].size(); i++)
//            cout<<adj[node][i]<<" ";
//   }
    
    int connectedComponents ()
    {
        for (int i = 1; i <= get_no_nodes(); i++)
            if (!visited[i])
            {
                cc++;
                DFS(i);
            }
        return cc;
    }
    
}g;
int main(int argc, const char * argv[]) {

    g.addEdge_ug();
    output<<g.connectedComponents();
}