Cod sursa(job #1626698)

Utilizator TibixbAndrei Tiberiu Tibixb Data 3 martie 2016 11:19:06
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
vector<int> L[100005], bc[100005];
stack<pair<int, int> > st;
pair<int, int> top;
int n, m, i, x, y, nbc, j, low[100005], niv[100005], tnod, tfiu;
void biconex(int nod, int fiu)
{
    nbc++;
    do
    {
        top=st.top();
        tnod=top.first;
        tfiu=top.second;
        bc[nbc].push_back(tfiu);
        st.pop();
    }
    while(tnod!=nod && tfiu!=fiu);
    bc[nbc].push_back(nod);
}
void dfsx(int nod, int lvl, int tata)
{
    low[nod]=niv[nod]=lvl;
    for(int i=0; i<L[nod].size(); i++)
    {
        int fiu=L[nod][i];
        if(fiu!=tata)
        {
            if(niv[fiu]==0)
            {
                st.push(make_pair(nod, fiu));
                dfsx(fiu, lvl+1, nod);
                low[nod]=min(low[nod], low[fiu]);
                if(low[fiu]>=niv[nod])
                    biconex(nod, fiu);
            }else
            {
                low[nod]=min(low[nod], low[fiu]);
            }
        }
    }
}
ifstream in("biconex.in");
ofstream out("biconex.out");
int main()
{
    in>>n>>m;
    for(i=1; i<=m; i++)
    {
        in>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    dfsx(1, 1, 0);
    out<<nbc<<"\n";
    for(i=1; i<=nbc; i++)
    {
        for(j=0; j<bc[i].size(); j++)
            out<<bc[i][j]<<" ";
        out<<"\n";
    }
    return 0;
}