Cod sursa(job #2557123)

Utilizator ArkinyStoica Alex Arkiny Data 25 februarie 2020 15:43:50
Problema Componente biconexe Scor 42
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
	
#include<fstream>
#include<iostream>
#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);
    
    for(auto& neighbor: G[x])
    {
        if(!viz[neighbor])
        {
            tarjan(neighbor, x);
            
            M[x][1] = min(M[x][1], M[neighbor][1]);
            
             
             if(M[x][0] <=  M[neighbor][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;
}