Cod sursa(job #2097710)

Utilizator RazorBestPricop Razvan Marius RazorBest Data 1 ianuarie 2018 14:01:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

vector<int> a[100001];
int noduri[100001];
int n, m, x, y;
vector<int> cmp[100001];
stack<pair<int, int> > st;
int cmp_len = 0;

template <class T>
void init_array(T a[], int n, T val)
{
    for (int i = 0; i < n; i++)
        a[i] = val;
}

int bfs(int parrent, int nod, int len)
{
    int mn = 0;
    noduri[0] = 0x7fffffff;

    noduri[nod] = len;

    for (unsigned int i = 0; i < a[nod].size(); i++)
    {
        int fiu = a[nod][i];
        if (noduri[fiu] == -1)
        {
            st.push(make_pair(nod, fiu));

            int mini = bfs(nod, fiu, len + 1);

            if (noduri[mini] < noduri[mn])
                mn = mini;
            if (noduri[mini] > len || (noduri[mini] == len && nod != parrent))
            {
                while (st.top().first != nod || st.top().second != fiu)
                {
                    cmp[cmp_len].push_back(st.top().second);
                    st.pop();
                }
                cmp[cmp_len].push_back(st.top().second);
                cmp[cmp_len++].push_back(st.top().first);
                st.pop();
            }
        }
        else if (noduri[fiu] < noduri[mn] && fiu != parrent)
            mn = fiu;
    }

    return mn;
}

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

    init_array(noduri, n + 1, -1);

    bfs(1, 1, 0);

    if (st.size())
    {
        while (st.size() > 1)
        {
            cmp[cmp_len].push_back(st.top().second);
            st.pop();
        }
        cmp[cmp_len].push_back(st.top().second);
        cmp[cmp_len++].push_back(st.top().first);
    }

    fout << cmp_len << '\n';
    for (int i = 0; i < cmp_len; i++)
    {
        for (unsigned int j = 0; j < cmp[i].size(); j++)
            fout << cmp[i][j] << ' ';
        fout << '\n';
    }

    return 0;
}