Cod sursa(job #1594291)

Utilizator metrix007Lungu Ioan Adrian metrix007 Data 9 februarie 2016 13:20:28
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>
#define NMAX 100005
using namespace std;

int n,m,x,y,fiu;
vector<int> a[NMAX];
vector<vector<int> >sol;
stack<pair<int,int> > stiva;
int dfn[NMAX],low[NMAX],nr;

ifstream in("biconex.in");
ofstream out("biconex.out");

void afisare(int x1, int y1)
{
    vector<int> coada;
    int xx = stiva.top().first; int yy = stiva.top().second;
    do
    {
    xx = stiva.top().first;  yy = stiva.top().second;
    stiva.pop();
    coada.push_back(xx);
    coada.push_back(yy);

    }
    while((xx!=x1 || yy !=y1) &&!stiva.empty());
    {

    }
    sort(coada.begin(),coada.end());
    coada.erase(unique(coada.begin(),coada.end()),coada.end());
    sol.push_back(coada);

}

void af()
{
    out << sol.size() << '\n';
    for(int i=0;i<sol.size();i++)
    {
        for(int j=0;j<sol[i].size();j++)
            out << sol[i][j] << " ";
        out << "\n";
    }
}

void biconex(int nod,int tnod)
{
    dfn[nod] = low[nod] = ++nr;
    int fiu;
    for(int i=0;i<a[nod].size();i++)
    {
        fiu = a[nod][i];
        if(fiu == tnod)
            continue;

        if(dfn[fiu]==-1)
        {

            stiva.push(make_pair(fiu,nod));
            biconex(fiu,nod);

            low[nod] = min(low[nod],low[fiu]);

            if(dfn[nod]<=low[fiu])
            {
                afisare(fiu,nod);
            }
        }
        else
            low[nod] = min(dfn[fiu],low[nod]);
    }
}



int main()
{
    in >> n >> m;
    for(int i=0;i<m;i++)
    {
        in >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }

    for(int i=1;i<=n;i++)
    {
        dfn[i] = -1;
    }
    biconex(1,-1);
    af();
    return 0;
}