Cod sursa(job #2557039)

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

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

vector<vector<int> > components;

vector<int> G[200010];

int M[200010][2];
int viz[200010];

int nr = 0;

vector<int> stack;

int in_stack[200010];

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

    M[x][0] = M[x][1] = nr;
    
    in_stack[x]  = 1;
    
    stack.push_back(x);
    int mn = nr;
    
    for(auto& neighbor: G[x])
    {
        if(!viz[neighbor])
        {
            tarjan(neighbor);
            
            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());
                    
                    in_stack[stack.back()] = 0;
                    stack.pop_back();
                }
                
                comp.push_back(x);
                
                components.push_back(comp);
            }
        }
        else if(in_stack[neighbor])
        {
             mn = min(mn, M[neighbor][1]);
        }
    }
   
    M[x][1] = mn;
    
}

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);
    
    out << components.size() <<"\n";
    
    for(auto& comp:components)
    {
        for(auto& node:comp)
        {
            out << node <<" ";
        }
        
        out<<"\n";
    }
    
    
    return 0;
}