Cod sursa(job #1404678)

Utilizator Denisa13Stefan Denisa Denisa13 Data 28 martie 2015 14:13:08
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

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

struct muchie
{   int x, y;
};

vector<int> G[100001];
stack<muchie> stiva; //stiva cu muchii
set<int> sol[100001]; //solutia retinuta ca set pentru a pastra ordinea crescatoare
set<int>::iterator it;
bool viz[100001];
int nr, tata[100001], nivel[100001], L[100001];

void DFS(int nod)
{   viz[nod]=1;
    L[nod]=nivel[nod];
    vector<int>::iterator it;
    for (it=G[nod].begin(); it!=G[nod].end(); it++)
        if (*it!=tata[nod])
        {
            if (viz[*it]==0)
            {
                muchie a;
                a.x=nod;
                a.y=*it;
                stiva.push(a);
                nivel[*it]=1+nivel[nod]; //nivelul in arborele DFS
                tata[*it]=nod; //tatal nodului e vf din care e descoperit
                DFS(*it);
                L[nod]=min(L[nod], L[*it]); //actualizam L pentru nod in cazul in care in recursivitate fiul sau a intrat intr-o componenta biconexa cu nivel mai mic
                if (L[*it]>=nivel[nod]) //"=" cand e ciclu; ">" cand e muchie
                {   ++nr;
                    int i, j;
                    while (i!=nod || j!=*it)
                    {   i=stiva.top().x;
                        j=stiva.top().y;
                        stiva.pop();
                        sol[nr].insert(i);
                        sol[nr].insert(j);
                    }
                }
            }
            else
                L[nod]=min(L[nod], nivel[*it]); //toate componentele unui ciclu pastreaza acelasi L=nivel primului element descoperit din ciclu
        }
}

int main()
{
    int n,m,i,x,y;
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    nivel[1]=1;
    DFS(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;
}