Cod sursa(job #2202058)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 7 mai 2018 13:55:13
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 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, 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;
    int xx, yy;
    bitset <100005> ap;
    do{
        xx=st.top().x;
        yy=st.top().y;
        if(ap[xx]==0) ap[xx]=1, bix[nrbix].push_back(xx);
        if(ap[yy]==0) ap[yy]=1, bix[nrbix].push_back(yy);
        st.pop();
    }
    while(xx!=i || yy!=u);
}

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
        {
            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++)
    {
        sort(bix[i].begin(),bix[i].end());
        for(auto j : bix[i]) fout<<j<<' ';
        fout<<'\n';
    }
    return 0;
}