Cod sursa(job #2097707)

Utilizator RazorBestPricop Razvan Marius RazorBest Data 1 ianuarie 2018 13:57:24
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.98 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

vector<int> a[100001];
int noduri[100001], len_s;
int n, m, x, y;
//bool art[100001];
vector<int> cmp[100001];
//vector<pair<int, int> > muchii;
stack<pair<int, int> > st;
int cmp_len = 0, muchii_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))
            {
                /*if (noduri[mini] > len)
                {
                    muchii.push_back(make_pair(nod, fiu));
                }

                art[nod] = 1;*/
                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;
    }

    //if (a[nod].size() < 2 && parrent == nod) art[nod] = false;

    return mn;
}

int main()
{
    int p = 1;

    //fin >> p >> n >> m;
    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);
    }

    if (p == 1)
    {
        fout << cmp_len << '\n';
        for (int i = 0; i < cmp_len; i++)
        {
            //fout << cmp[i].size() << ' ';
            for (unsigned int j = 0; j < cmp[i].size(); j++)
                fout << cmp[i][j] << ' ';
            fout << '\n';
        }
    }
    /*else if (p == 2)
    {
        int cnt = 0;
        for (int i = 1; i <= n; i++)
            if (art[i]) cnt++;

        fout << cnt << '\n';
        for (int i = 1; i <= n; i++)
            if (art[i]) fout << i << ' ';
    }
    else if (p == 3)
    {
        fout << muchii.size() << '\n';
        for (int i = 0; i < muchii.size(); i++)
            fout << muchii[i].first << ' ' << muchii[i].second << '\n';
    }*/

    return 0;
}