Cod sursa(job #1922424)

Utilizator Vally77FMI Calinescu Valentin Gelu Vally77 Data 10 martie 2017 17:24:54
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.67 kb
#include <list>
#include <fstream>
#include <set>
#include <stack>
using namespace std;
ifstream ka("biconex.in");
ofstream ki("biconex.out");
int* ciclu_min;
int n;
int* nivel;
list<int> *graf;
list<int> *solutie;
bool* vizitat;
bool *folosit;
stack< pair<int, int> >stiva;

int cate;

void DFS(int t)
{
    vizitat[t] = true;
    ciclu_min[t] = nivel[t];
    for(list<int>::iterator it = graf[t].begin(); it != graf[t].end(); ++it)
    {
        if(vizitat[*it] == false)
        {
            nivel[*it] = nivel[t] + 1;
            stiva.push(make_pair(t, *it));
            DFS(*it);
            ciclu_min[t] = min(ciclu_min[t], ciclu_min[*it]);
            if(ciclu_min[*it] >= nivel[t])
            {
                cate++;
                while(!stiva.empty() && (stiva.top().first != t || stiva.top().second != *it))
                {
                   if(!folosit[stiva.top().first])
                    {
                        solutie[cate].push_back(stiva.top().first);
                        folosit[stiva.top().first] = true;
                    }
                   if(!folosit[stiva.top().second])
                    {
                        solutie[cate].push_back(stiva.top().second);
                        folosit[stiva.top().second] = true;
                    }
                   stiva.pop();
                }
                if(!stiva.empty())
                {
                    if(!folosit[t])
                    {
                        solutie[cate].push_back(t);
                        folosit[t] = true;
                    }
                    if(!folosit[*it])
                    {
                        solutie[cate].push_back(*it);
                        folosit[*it] = true;
                    }
                    stiva.pop();
                }
                for(int i = 1; i <= n; i++)
                    folosit[i] = false;
            }
        }
        else if(nivel[*it] < nivel[t] - 1)
            ciclu_min[t] = min(ciclu_min[t], nivel[*it]);
    }
}

int main()
{
    int m;
    ka >> n >> m;
    ciclu_min = new int[n + 1];
    nivel = new int[n + 1];
    vizitat = new bool[n + 1];
    folosit = new bool[n + 1];
    graf = new list<int>[n + 1];
    solutie = new list<int>[n + 1];
    for(int i = 1; i <= n; i++)
    {
        vizitat[i] = false;
        folosit[i] = false;
    }
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        ka >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    nivel[1] = 1;
    DFS(1);
    ki << cate << '\n';
    for(int i = 1; i <= cate; i++)
    {
        for(list<int>::iterator it = solutie[i].begin(); it != solutie[i].end(); ++it)
            ki << *it << " ";
        ki << '\n';
    }
}