Cod sursa(job #2662745)

Utilizator BGondaGonda George Luis Bogdan BGonda Data 24 octombrie 2020 13:32:10
Problema Componente biconexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>
#include <tuple>

using namespace std;

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

using VI  = vector<int>;
using SI  = set<int>;
using VVI  = vector<VI>;

int n, m, a, b;
int nv;
VVI G;
vector<SI> cbc;
SI c;

VI niv, L;
stack<pair<int, int>> stk;

void Tarjan(int nod, int tata);

int main()
{
    fin >> n >> m;

    G = VVI(n + 1);
    niv = L = VI(n + 1);

    for ( int i = 1; i <= m; ++i )
    {
        fin >> a >> b;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }


    for ( int i = 1; i <= n; ++i )
        if ( niv[i] == 0 )
           Tarjan(i, 0);

    fout << cbc.size() << "\n";

	for (const auto& c : cbc)
    {
		for (const auto& x : c)
			fout << x << ' ';
		fout << '\n';
	}

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

void Tarjan(int x, int tata)
{
    niv[x] = L[x] = ++nv;

    for ( const auto& y : G[x] )
    {
		if (y == tata) continue;

        if ( niv[y] == 0 ) // muchie de arbore
        {
			stk.push({x, y});

            Tarjan(y, x);


            if (L[y] >= L[x])
            {
				c.clear();
				int a, b;
				while (true)
				{
					tie(a, b) = stk.top();
					stk.pop();
					c.insert(a); c.insert(b);
					if (a == x && b == y)
						break;
				}

				cbc.push_back(c);
			}

			 L[x] = min(L[x], L[y]);
        }
        else  // daca este back edge (nu exista cross edge la GN)
                L[x] = min(L[x], niv[y]);
	}
}