Cod sursa(job #2665275)

Utilizator iulia_caciucunescuIulia Caciucunescu iulia_caciucunescu Data 30 octombrie 2020 14:52:57
Problema Componente biconexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;

stack<pair<int, int> > sol;
vector<set<int> > comp;
void punct_critic(int start, int tata, int niv, vector<vector<int> > adiacenta, vector<int> &viz, vector<int> &minim)
{
	minim[start] = niv;
	viz[start] = niv;

	for(int nod: adiacenta[start])
	{
		if(viz[nod] == 0)
		{
			sol.push(make_pair(start, nod));
			punct_critic(nod, start, niv+1, adiacenta, viz, minim);
			minim[start] = min(minim[start], minim[nod]);
			if(minim[nod] >= viz[start])
			{
				set<int> aux;
				while(sol.top().first != start || sol.top().second != nod)
				{
					aux.insert(sol.top().first);
					aux.insert(sol.top().second);
					sol.pop();
				}
				aux.insert(sol.top().first);
				aux.insert(sol.top().second);
				sol.pop();
				comp.push_back(aux);
				aux.clear();
			}
		}
		else
			minim[start] = min(minim[start], viz[nod]);
	}
}

int main()
{
    ifstream in("biconex.in");
    ofstream out("biconex.out");
    int n,m;
    in>>n>>m;
    vector<vector<int> > matrice(n+1, vector<int> (n+1, 0));
    vector<vector<int> > adiacenta(n+1);
    vector<int> viz(n+1, 0);
    vector<int> minim (n+1, 0);
    vector<bool> critic (n+1, false);
    for(int i=1; i<=m; i++)
    {
        int x,y,c;
        in>>x>>y;
        matrice[x][y] = matrice[y][x] = 1;
        adiacenta[x].push_back(y);
        adiacenta[y].push_back(x);
    }

    punct_critic(1, 0, 1, adiacenta, viz, minim);

    out<<comp.size()<<endl;
    for(int i=0; i<comp.size(); i++)
    {
        for(int nod : comp[i])
            out<<nod<<" ";
        out<<endl;
    }
}