Cod sursa(job #1985378)

Utilizator sebinechitasebi nechita sebinechita Data 27 mai 2017 18:28:30
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#define MAX 100010
#define mp make_pair
#define cout fout
vector <int> G[MAX];
vector <pair<int, int> > st;
vector <vector<int> > comp;
int viz[MAX], lvl[MAX], up[MAX];

void dfs(int nod, int dad){
    lvl[nod] = lvl[dad] + 1;
    up[nod] = lvl[nod];
    viz[nod] = 1;
    for(auto v : G[nod]){
        if(v == dad)
            continue;
        if(!viz[v]){
            st.push_back(mp(nod, v));
            dfs(v, nod);
            up[nod] = min(up[nod], up[v]);
            if(up[v] >= lvl[nod]){
                vector<int> aux;
                while(st.back() != mp(nod, v)){
                    aux.push_back(st.back().second);
                    st.pop_back();
                }
                st.pop_back();
                aux.push_back(v);
                aux.push_back(nod);
                comp.push_back(aux);
            }
        }
        else{
            up[nod] = min(up[nod], lvl[v]);
        }
    }
}

int main(){
    int n, m, i, x, y;
    fin >> n >> m;
    for(i = 1 ; i <= m ; i++){
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(i = 1 ; i <= n ; i++){
        if(!viz[i]){
            dfs(i, 0);
        }
    }
    cout << comp.size() << "\n";
    for(auto c : comp){
        for(auto it : c){
            cout << it << " ";
        }
        cout << "\n";
    }
}