Cod sursa(job #2200491)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 1 mai 2018 16:14:49
Problema Componente biconexe Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

int n, m, nrbix, nrc, tmp, d[100001], l[100001];
vector <int> a[100001];
vector <int> bix[100001];
stack <pair<int,int>> st;

void CompBiconexa(int i, int u){
    ++nrbix;
    do{
        bix[nrbix].push_back(st.top().x);
        st.pop();
    }
    while(st.top().x!=i && st.top().y!=u);
    bix[nrbix].push_back(st.top().x);
}

void Biconex(int u, int tu){
    d[u]=l[u]=++tmp;
    ///parcurg lista de adiacenta a lui u
    for(auto i : a[u]){
        if(i!=tu && d[i]<d[u]) st.push(make_pair(i,u));
        if(d[i]==-1) ///i nevizitat
        {
            if(u==1) nrc++;
            Biconex(i,u);
            l[u]=min(l[u],l[i]);
            if(l[i]>=d[u]) CompBiconexa(i,u);
        }
        else if(i!=tu) l[u]=min(l[u],d[i]);
    }
}

int main()
{
    int i, j;
    fin>>n>>m;
    while(m--){
        fin>>i>>j;
        a[i].push_back(j);
        a[j].push_back(i);
    }
    for(i=1; i<=n; i++) d[i]=-1;
    st.push(make_pair(1,-1));
    Biconex(1,-1);
    fout<<nrbix<<'\n';
    for(i=1; i<=nrbix; i++)
    {
        for(auto j : bix[i]) fout<<j<<' ';
        fout<<'\n';
    }
    return 0;
}