Cod sursa(job #2118233)

Utilizator vladttturcuman vlad vladtt Data 30 ianuarie 2018 13:24:23
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
//
//  main.cpp
//  CompetitiveProgramming
//
//  Created by Vlad Turcuman on 29/01/2018.
//  Copyright © 2018 Vlad Turcuman. All rights reserved.
//

#include <fstream>
#include <vector>

#define NMax 100
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");

vector<int> stack;

vector<vector<int> > result;
int lvl[NMax];

vector<int> v[NMax];

void Remove(int until, int add){
    result.push_back(* new vector<int>);
    result[result.size()-1].push_back(add);
    
    while(stack.back() != until)
        result[result.size()-1].push_back(stack.back()),
        stack.pop_back();
    
    result[result.size()-1].push_back(stack.back()),
    stack.pop_back();
}

int dfs(int ant,int node,int lvl){
    
    ::lvl [node] = lvl;
    stack.push_back(node);
    
    int up = lvl-1;
    
    for(auto it : v[node]){
        if(it == ant) continue;
        if(::lvl[it] != 0)
            up = min(up, ::lvl[it]);
        else{
            int x = dfs(node, it, lvl+1);
            if(x == lvl)
                Remove(it, node);
            else
                up = min(up, x);
        }
    }
    return up;
}

int main() {
    int n,m,a,b;
    
    cin>>n>>m;
    
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    dfs(0,1,1);
    
    if(stack.size() > 1)
        Remove(stack[1], stack[0]);
    
    cout<<result.size()<<'\n';
    for(auto it : result){
        sort(it.begin(),it.end());
        for(auto it2 : it)
            cout<<it2<< ' ';
        cout<<'\n';
    }
    
    return 0;
}