Cod sursa(job #2557050)

Utilizator ArkinyStoica Alex Arkiny Data 25 februarie 2020 14:28:42
Problema Componente biconexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include<fstream>
#include<vector>
using namespace std;

ifstream in("biconex.in");
ofstream out("biconex.out");

vector<vector<int> > components;

vector<int> G[100010];

int M[100010][2];
int viz[100010];

int nr = 0;

vector<int> stack;


void tarjan(int x, int f)
{
    ++nr;
    viz[x] = 1;

    M[x][0] = M[x][1] = nr;
    
    stack.push_back(x);
    int mn = nr;
    
    for(auto& neighbor: G[x])
    {
        if(!viz[neighbor])
        {
            tarjan(neighbor, x);
            
            M[x][1] = min(M[x][1], M[neighbor][1]);
            mn = min(mn, M[x][1]);
            
             
             if(M[x][0] == M[x][1])
            {
                vector<int> comp;
                while(stack.back() != x)
                {
                    comp.push_back(stack.back());
                    stack.pop_back();
                }
                
                comp.push_back(x);
                
                components.push_back(comp);
            }
        }
        else if(neighbor != f)
        {
             M[x][1] = min(M[x][1], M[neighbor][1]);
        }
    }
   
    
}

int main()
{
    int N,M;
    
    in >> N >> M;
    
    for(int i=1;i<=M;++i)
    {
        int x, y;
        
        in >> x >> y;
        
        G[x].push_back(y);
        G[y].push_back(x);
    }
    
    tarjan(1, 0);
         
    
    out << components.size() <<"\n";
    
    for(auto& comp:components)
    {
        for(auto& node:comp)
        {
            out << node <<" ";
        }
        
        out<<"\n";
    }
    
    
    return 0;
}