Cod sursa(job #1540410)

Utilizator TibixbAndrei Tiberiu Tibixb Data 2 decembrie 2015 19:23:14
Problema Componente biconexe Scor 42
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include<fstream>
#include<vector>
#include<deque>
#include<algorithm>
using namespace std;
vector <int> L[100000], sol[100000];
deque <pair<int, int> > q;
pair <int, int> top;
int n, m, x, y, i, j, nrsol, low[100000], dfx[100000];
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)
{
    low[nod]=dfx[nod]=niv;
    for(int i=0; i<L[nod].size(); i++)
    {
        int fiu=L[nod][i];
        if(dfx[fiu]==0)
        {
            q.push_back(make_pair(nod, fiu));
            dfsx(fiu, niv+1);
            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);
    out<<nrsol<<"\n";
    for(i=1; i<=nrsol; i++)
    {
        sort(sol[i].begin(), sol[i].end());
        for(j=0; j<sol[i].size()-1; j++)
        {
            if(sol[i][j]!=sol[i][j+1])
                out<<sol[i][j]<<" ";
        }
        if(sol[i][j]!=sol[i][j-1])
            out<<sol[i][j];
        out<<"\n";
    }
    return 0;
}