Cod sursa(job #2793159)

Utilizator dascalu_maraDascalu Mara Elena dascalu_mara Data 3 noiembrie 2021 09:49:23
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.25 kb
//
//  main.cpp
//  Componente biconexe
//
//  Created by Mara Dascalu on 30/10/2021.
//

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

using namespace std;

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


 class Graph
{
    int nodes, edges;
    vector<int> adj[100010];
    bool visited[100010] = {0};
    int cost[100010];
    queue<int> queue_bfs;
    vector<int> bcc[100010]; //vectorul care stocheaza componentele biconexe
    int current = 0;
    int level[100010] = {0};
    int low_level[100010] = {0};
    stack<pair<int, int>> component_node;

public:
    
    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 afis_adj(int node){
     //       for (int i = 0; i < adj[node].size(); i++)
     //            cout<<adj[node][i]<<" ";
     //   }

    void DFS(int node)
    {
        visited[node] = 1;
        //output<<node<<" ";
 
        for (int i = 0; i < adj[node].size(); i++)
            if( !visited[i])
                DFS(i);
    }
    
    void BFS (int node)
    {
        memset(cost,  -1, sizeof(cost));
        visited[node] = 1; //marchez nodul curent ca vizitat
        queue_bfs.push(node);
        cost[node] = 0;

        while (!queue_bfs.empty()) {
            node = queue_bfs.front(); //iau nodul din varful cozii
            queue_bfs.pop();

            for (int i = 0; i < adj[node].size(); i++) //parcurg toti vecinii sai
                if ( !visited[adj[node][i]]) //daca sunt nevizitati
                {
                    visited[adj[node][i]] = 1;  //ii marchez ca vizitati
                    queue_bfs.push(adj[node][i]);   //ii adaug in coada
                    cost[adj[node][i]] = cost[node] + 1;   //calculez costul raportat la "parintele" sau
                }
        }
    }

    void out_cost (int no)
    {
        for (int i = 1; i <= no; i++)
        output<<cost[i]<<" ";
    }
    
    void DFS(int node, int parent)
    {
        visited[node] = 1;
     
     
        level[node] = level[parent] + 1;
        low_level[node] = level[node];
        int child;
     
        int dim = adj[node].size();
        for ( int i = 0; i< dim ; i++)
        {
     
     
            child = adj[node][i];
            if (child != parent)
            {
                if (visited[child] == true)  //daca fiul sau a fost deja parcurs si nu este tatal nodului curent, muchia (fiu,nod) este muchie de intoarcere
                {
                    //cout<<"true "<<node<<" "<<*iter<<" "<<level[*iter]<<"\n";
                    if(level[child] < low_level[node])low_level[node] = level[child];  //actualizam valoarea low_level[nod] daca fiul sau se afla mai sus decat el (p[t ca avem muchie de intoarcere
                }
                else //daca fiul sau nu a fost inca parcurs, continuam DFS din fiu
                {
                    component_node.push({node, child});
                    //cout<<"inainte de dfs"<<node<<" "<<*iter<<" "<<level[*iter]<<"\n";
                    DFS(child, node);
     
                    //cout<<"dupa dfs"<<*iter<<" "<<level[*iter]<<"\n";
                    if (low_level[child] < low_level[node])
                        low_level[node] = low_level[child]; //daca la intoarcerea din apel fiul are un nivel de intoarcere mai mic decat al nodului, actualizam low_level[node]
     
                    if (low_level[child] >= level[node])
                    {
                        while( component_node.top().first != node)
                        {
                            bcc[current].push_back(component_node.top().second);
                            component_node.pop();
                        }
                        bcc[current].push_back(component_node.top().second);
                        bcc[current].push_back(component_node.top().first);
                        component_node.pop();
                        //bcc[current].push_back(node);
                        current++;
     
                    }

                }
            }
        }
    }
    void biconnectedComponents()
    {
        output<<current << "\n";
            for (int i =0 ; i <= current; i++)
                {
                    for (int j = bcc[i].size() - 1; j >= 0; j--)
                        if(bcc[i][j])
                            output<<bcc[i][j]<<" ";
                    output<<"\n";
                }
    }
    
}g;


int main(int argc, const char * argv[]) {
    
    g.addEdge_ug();
    g.DFS(1, 0);
    g.biconnectedComponents();

    return 0;
}