Cod sursa(job #1391486)

Utilizator mateidanutDanut Gabriel Matei mateidanut Data 17 martie 2015 23:20:18
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>
#define NMAX 100001
using namespace std;

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

struct muchie
{   int x, y;
};

vector<int> G[NMAX];
stack<muchie> St;
set<int> sol[NMAX];
set<int>::iterator it;

int n, m, i, j, nr, U[NMAX], T[NMAX], niv[NMAX], L[NMAX];

void DF(int nod)
{   U[nod]=1;
    L[nod]=niv[nod];
    vector<int>::iterator it;
    for (it=G[nod].begin(); it!=G[nod].end(); ++it)
        if (*it!=T[nod])
        {   if (!U[*it])
            {   muchie a;
                a.x=nod;
                a.y=*it;
                St.push(a);
                niv[*it]=1+niv[nod];
                T[*it]=nod;
                DF(*it);
                L[nod]=min(L[nod], L[*it]);
                if (L[*it]>=niv[nod])
                {   ++nr;
                    int i, j;
                    while (i!=nod || j!=*it)
                    {   i=St.top().x;
                        j=St.top().y;
                        St.pop();
                        sol[nr].insert(i);
                        sol[nr].insert(j);
                    }
                }
            }
            else
                L[nod]=min(L[nod], niv[*it]);
        }
}

int main()
{   f>>n>>m;
    for (; m; --m)
    {   f>>i>>j;
        G[i].push_back(j);
        G[j].push_back(i);
    }
    niv[1]=1;
    DF(1);
    g<<nr<<'\n';
    for (i=1; i<=nr; ++i)
	{	for (it=sol[i].begin(); it!=sol[i].end(); ++it)
			g<<*it<<' ';
		g<<'\n';
	}
    return 0;
}