Cod sursa(job #2493128)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 16 noiembrie 2019 08:32:12
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>
#define N 100005

using namespace std;

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

int n, m, nivel[N], nivelMin[N];
bool viz[N];
stack < pair <int, int> > st;
vector <int> L[N];
vector < unordered_set<int> > comp;

void findComp(int nod, int nextNod)
{
    unordered_set<int> C;
    int firstNode, secondNode;
    do
    {
        firstNode = st.top().first;
        secondNode = st.top().second;
        st.pop();

        C.insert(firstNode);
        C.insert(secondNode);
    }while (firstNode != nod || secondNode != nextNod);

    comp.push_back(C);
}

void DFS(int nod, int tata)
{
    viz[nod] = 1;
    nivel[nod] = nivel[tata] + 1;
    nivelMin[nod] = nivel[nod];

    for (auto nextNod : L[nod])
    {
        if (nextNod != tata)
        {
            if (viz[nextNod])
                nivelMin[nod] = min(nivelMin[nod], nivel[nextNod]);
            else
            {
                st.push(make_pair(nod, nextNod));
                DFS(nextNod, nod);

                nivelMin[nod] = min(nivelMin[nod], nivelMin[nextNod]);
                if (nivelMin[nextNod] >= nivel[nod])
                    findComp(nod, nextNod);
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        fin >> a >> b;
        L[a].push_back(b);
        L[b].push_back(a);
    }

    DFS(1, 0);

    fout << comp.size() << "\n";
    for (unsigned i = 0; i < comp.size(); i++)
    {
        for (auto j : comp[i])
            fout << j << " ";
        fout << "\n";
    }
    return 0;
}