Cod sursa(job #2662800)

Utilizator BGondaGonda George Luis Bogdan BGonda Data 24 octombrie 2020 15:13:50
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
// O(n + m)
// c++98, c++11, C++14, c++17, c++20
#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] >= niv[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]);            
	}
}