Cod sursa(job #2791889)

Utilizator dascalu_maraDascalu Mara Elena dascalu_mara Data 31 octombrie 2021 12:20:43
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.89 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("biconex.in");
ofstream output("biconex.out");
 
//class Edge{
//public:
//    int u;
//    int v;
//    Edge(int u, int v){
//        this->u = u;
//        this->v = v;
//    }
//};
 
 class Graph
{
    int nodes, edges;
    vector<int> adj[100010];
    int cost[1001];
    queue<int> queue_bfs;
    list<int>:: iterator iter;
    int level[100010] = {0};
    int low_level[100010] = {0};
    stack<pair<int, int>> component_node;
 
public:
 
    bool visited[100010] = {0};
    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 a, int b)
    {
        adj[a].push_back(b);
    }
 
    void addEdge_ug (int a, int b)
    {
        adj[a].push_back(b);
//        adj[a].sort();
        adj[b].push_back(a);
//        adj[b].sort();
    }
/*
    void DFS(int node)
    {
        visited[node] = 1;
        //output<<node<<" ";
 
        for (iter = adj[node].begin(); iter != adj[node].end(); iter++)
            if( !visited[*iter])
                DFS(*iter);
    }
 
    void afis_adj(int node){
        list<int> :: iterator i;
        for(i = adj[node].begin(); i != adj[node].end(); i++)
            cout<<*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 (iter = adj[node].begin(); iter != adj[node].end(); iter++) //parcurg toti vecinii sai
                if ( !visited[*iter]) //daca sunt nevizitati
                {
                    visited[*iter] = 1;  //ii marchez ca vizitati
                    queue_bfs.push(*iter);   //ii adaug in coada
                    cost[*iter] = 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++;
 
                }
 
 
 
 
            }
        }
    }
}
 
}g;
 
 
int main(int argc, const char * argv[]) {
    int no_nodes, no_edges, n1, n2;
    input>>no_nodes>>no_edges;
    for (int i = 0 ; i < no_edges; i++)
    {
        input>>n1>>n2;
        g.addEdge_ug(n1, n2);
    }
 
 
    g.DFS(1, 0);
    output<< g.current << "\n";
    for (int i =0 ; i <= g.current; i++)
        {
            for (int j = g.bcc[i].size() - 1; j >= 0; j--)
                if(g.bcc[i][j])
                    output<<g.bcc[i][j]<<" ";
            output<<"\n";
        }
 
 
    return 0;
}