Cod sursa(job #2153799)

Utilizator DeleDelegeanu Alexandru Dele Data 6 martie 2018 14:36:41
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <vector>
#include <stack>
#define MAX 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<int> a[MAX];
vector< vector<int> > sol;
stack<int> st;
bool viz[MAX];
int nro[MAX],low[MAX],t[MAX];
int nrb,root;
int n,m,x,y;
void biconex(int x){
    viz[x]=true;
    nro[x]=low[x]=nro[ t[x] ]+1;
    st.push(x);

    for(int i=0 ; i<a[x].size() ; ++i)
    {
        int it=a[x][i];
        if(it==t[x])
            continue;
        if(viz[it])
        {
            low[x]=min(low[x],nro[it]);
            continue;
        }
        t[it]=x;
        biconex(it);
        low[x]=min(low[x],low[it]);

        if(nro[x]<=low[it])
        {
            sol.push_back(vector<int>(0));
            int z;
            do{
                z=st.top();
                st.pop();
                sol[nrb].push_back(z);
            }while(z!=it);
            sol[nrb].push_back(x);
            ++nrb;
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1 ; i<=m; ++i)
    {
        f>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }

    for(int i=1 ; i<=n ; ++i)
        if (!viz[i])
        {
            root=i;
            t[i]=0;
            biconex(i);
        }

    g<<nrb<<'\n';
    vector<int>::reverse_iterator rit;
    for(int i=0 ; i<sol.size() ; ++i)
    {
        for(rit=sol[i].rbegin() ; rit!=sol[i].rend() ; ++rit)
            g<<*rit<<" ";
        g<<'\n';
    }
    return 0;

}