Cod sursa(job #1540483)

Utilizator TibixbAndrei Tiberiu Tibixb Data 2 decembrie 2015 20:30:38
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<fstream>
#include<vector>
#include<deque>
#include<algorithm>
using namespace std;
vector <int> L[100010], sol[100010];
deque <pair<int, int> > q;
pair <int, int> top;
int n, m, x, y, i, j, nrsol, low[100010], dfx[100010], nrqq;
void biconex (int nod, int fiu)
{
    nrsol++;
    do
    {
        top=q.back();
        sol[nrsol].push_back(top.first);
        sol[nrsol].push_back(top.second);
        q.pop_back();
    }
    while(top.first!=nod && top.second!=fiu);
}
void dfsx (int nod, int niv, int tata)
{
    low[nod]=dfx[nod]=niv;
    for(int i=0; i<L[nod].size(); i++)
    {
        int fiu=L[nod][i];
        if(fiu!=tata)
        {
            if(dfx[fiu]==0)
            {
                q.push_back(make_pair(nod, fiu));
                dfsx(fiu, niv+1, nod);
                low[nod]=min(low[nod], low[fiu]);
                if(low[fiu]>=dfx[nod])
                    biconex(nod, fiu);
            }
            else
            {
                low[nod]=min(low[nod], dfx[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<<nrsol<<"\n";
    for(i=1; i<=nrsol; i++)
    {
        sort(sol[i].begin(), sol[i].end());
        for(j=0; j<sol[i].size(); j++)
        {
            if(sol[i][j]!=sol[i][j+1])
                out<<sol[i][j]<<" ";
        }
        out<<"\n";
    }
    return 0;
}