Cod sursa(job #1376175)

Utilizator darrenRares Buhai darren Data 5 martie 2015 16:24:45
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <cstring>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
vector<int> V[100002];
vector<vector<int> > COMP;
bool S[100002];
int niv[100002], minniv[100002];
int ST[100002];

void Dfs(int x)
{
    S[x] = true;
    minniv[x] = niv[x];
    ST[++ST[0]] = x;

    for (auto it = V[x].begin(); it != V[x].end(); ++it)
    {
        if (!S[*it])
        {
            niv[*it] = niv[x] + 1;
            Dfs(*it);

            if (minniv[*it] >= niv[x])
            {
                COMP.push_back(vector<int>());
                while (true)
                {
                    COMP.back().push_back(ST[ST[0]]);
                    --ST[0];
                    if (ST[ST[0] + 1] == x)
                        break;
                }
                ST[++ST[0]] = x;
            }
        }

        if (niv[*it] < niv[x])
            minniv[x] = min(minniv[x], niv[*it]);
        else
            minniv[x] = min(minniv[x], minniv[*it]);
    }
}

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

    fin >> N >> M;
    for (int i = 1, nod1, nod2; i <= M; ++i)
    {
        fin >> nod1 >> nod2;
        V[nod1].push_back(nod2);
        V[nod2].push_back(nod1);
    }

    for (int i = 1; i <= N; ++i)
        if (!S[i])
            Dfs(i);

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

    fin.close();
    fout.close();
}