Cod sursa(job #2791863)

Utilizator dascalu_maraDascalu Mara Elena dascalu_mara Data 31 octombrie 2021 11:52:10
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.71 kb
#include <bits/stdc++.h>
#include <iostream>
#define N  100010
using namespace std;
ifstream input("biconex.in");
ofstream output("biconex.out");
 
stack<pair<int, int>> component_node;
bool visited[N];
int level[N];
int low_level[N];
vector<int> adj[N];
vector<int> bcc[N];
int current;
 
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();
                    current++;
                    // cout << current;
                }
 
 
 
 
            }
        }
    }
}
 
int main() {
    // insert code here...
    int no_nodes, no_edges;
    int x, y;
    input >> no_nodes >> no_edges;
 
 
    for(int i = 1; i <= no_edges; ++i)
    {
        input >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
 
    }
 
 
    DFS(1, 0);
    output <<current<<"\n";
    
    for (int i =0 ; i <= current; i++)
        {
            for (int j = bcc[i].size(); j >= 0; j--)
            if(bcc[i][j])
                output<<bcc[i][j]<< " ";
            output<<"\n";
        }
    return 0;
}