Cod sursa(job #2441971)

Utilizator bluestorm57Vasile T bluestorm57 Data 22 iulie 2019 12:25:23
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
//Bye, Infoarena! I'll see you in the afternoon

#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100005;
int n,m,viz[NMAX],lvl[NMAX],low[NMAX];
vector<int> v[NMAX];
stack <int> s;
struct var{
    vector<int> v;
}ans[2 * NMAX];
int k;

void dfs(int nod){
    viz[nod] = 1;
    s.push(nod);
    for(auto it: v[nod])
        if(!viz[it]){
            lvl[it] = low[it] = lvl[nod] + 1;
            dfs(it);
            if(low[it] >= lvl[nod]){
                k++;
                while(s.top() != it){
                    ans[k].v.push_back(s.top());
                    s.pop();
                }
                s.pop();
                ans[k].v.push_back(it);
                ans[k].v.push_back(nod);
            }
            low[nod] = min(low[nod], low[it]);
        }else
            low[nod] = min(low[nod], lvl[it]);
}

int main(){
    int i,j,x,y;
    f >> n >> m;
    for(i = 1 ; i <= m ; i++){
        f >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for(i = 1 ; i <= n ; i++)
        if(!viz[i])
            dfs(i);

    g << k << "\n";

    for(i = 1 ; i <= k ; i++){
        for(j = 0 ; j < ans[i].v.size() ; j++)
            g << ans[i].v[j] << " " ;
        g << "\n";
    }

    return 0;
}