Cod sursa(job #2417147)

Utilizator radumihaisirbuSirbu Radu-Mihai radumihaisirbu Data 28 aprilie 2019 23:41:38
Problema Componente biconexe Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 1e5 + 5;

vector <int> v[nmax], low(nmax, 0), nivel(nmax, 0);

set <int> comp[nmax];

stack <pair <int, int> > st;

int n, m, x, y, cmp;

void update (int a, int b)
{
    cmp++;

    do
    {
        x = st.top().first;
        y = st.top().second;
        st.pop();
        comp[cmp].insert(x);
        comp[cmp].insert(y);
    } while(x != a || b != y);
}

void dfs (int nod = 1, int niv = 1, int father = 0)
{
   low[nod] = nivel[nod] = niv;
   for (vector <int> :: iterator it=v[nod].begin(); it!=v[nod].end(); ++it)
   {
       if (*it == father) continue;
       if (nivel[*it] == 0)
       {
           st.push(make_pair(nod, *it));
           dfs(*it, niv+1, nod);
           low[nod] = min(low[*it], low[nod]);
           if (low[*it] >= nivel[nod]) // se poate ajunge la un nod mai sus decat nod
           {
               update(nod, *it);
           }
       }
       else
       {
           low[nod] = min(low[nod], nivel[*it]);
       }
   }

}

int main()
{
    fin >> n >> m;
    while (m--)
    {
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs();
    fout << cmp << '\n';
    for (int i=1; i<=cmp; ++i)
    {
        for (set <int> :: iterator it=comp[i].begin(); it!=comp[i].end(); ++it)
            fout << *it << ' ';
        fout << '\n';
    }
    return 0;
}