Cod sursa(job #1477885)

Utilizator metrix007Lungu Ioan Adrian metrix007 Data 27 august 2015 12:19:13
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.48 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <algorithm>
#include <utility>
#define NMAX 100000
#define Min(a, b)  ((a) < (b) ? (a) : (b))
using namespace std;

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

int n,m,dfn[NMAX],low[NMAX],start=1,x,y,nro,c;
vector<int> a[NMAX];
stack< pair<int,int> > stiva;
vector< vector<int> > comp;

void citire()
{
    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=0;i<=n;i++)
        dfn[i]=-1;
}

void afisare(int x1, int y1)
{
    int xx,yy;
    vector<int> cont;
    do
    {
        xx = stiva.top().first;
        yy = stiva.top().second;
        stiva.pop();
        cont.push_back(xx);
        cont.push_back(yy);
    }
    while((xx!=x1 || yy!=y1));
    comp.push_back(cont);
}


void biconex(int nod, int tnod)
{
    int fiu;
    dfn[nod]=low[nod]=nro++;

    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(nod,fiu));

            biconex(fiu,nod);
            low[nod] = Min(low[nod],low[fiu]);

            if(low[fiu]>=dfn[nod])
            {
               // cout << nod << " " << tnod << endl;
               afisare(nod,fiu);
            }
        }

        else
            low[nod] = Min(low[nod],dfn[fiu]);
    }
}


void af()
{
    out << comp.size() << "\n";
    for(int i=0;i<comp.size();i++)
    {
        sort(comp[i].begin(),comp[i].end());
        comp[i].resize(unique(comp[i].begin(),comp[i].end())-comp[i].begin());
        for(int j=0;j<comp[i].size();j++)
            out << comp[i][j] << " ";
        out << "\n";
    }
}

int main()
{
    citire();
    biconex(1,-1);
    af();
    return 0;
}

/*
void biconex(int nod, int tnod)
{
    int fiu;
    dfn[nod]=low[nod]=nro++;

    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(nod,fiu));

            biconex(fiu,nod);
            low[nod] = Min(low[nod],low[fiu]);

            if(low[fiu]>=dfn[nod])
            {
                cout << nod << " " << tnod << endl;
              //  afisare(nod,fiu);
            }
        }

        else
            low[nod] = Min(low[nod],dfn[fiu]);
    }
}*/