Cod sursa(job #1904582)

Utilizator Cudrici_CarinaCudrici Carina Cudrici_Carina Data 5 martie 2017 17:44:40
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream fi("biconex.in");
ofstream fo("biconex.out");

const int MAX = 100001;
set<int> comp[MAX];
vector<int> G[MAX];
stack<pair<int,int>> st;
int n,m,sol,root;
bool p[MAX];     // p[i] == true daca i e pct. articulatie
int t[MAX];     // sir de tati
int index[MAX];   // indexelul fiecarui nod in arborele DF
int L[MAX];     // nivel minim in arbore pe care se p ajung dintr-un nod sau
                // dintr-unul dintre descendentii lui
                // printr-o singura muchie de intoarcere
int nr;         // Nr de muchii "de arbore" (care "ies" din radacina)


void Read()
{
	int x, y;
	fi >> n >> m;
	while ( fi >> x >> y )
	{
		G[x].push_back(y);
		G[y].push_back(x);
	}
}
void Extract(int x, int y)
{
    sol++;
    int xs, ys;
    do
    {   xs = st.top().first; ys = st.top().second;
        comp[sol].insert (xs);
        comp[sol].insert (ys);
        st.pop();
    }
    while (xs != x || ys != y);

}
void DF(int x, int niv)
{
	if ( niv == 2 ) nr++;
	L[x] = index[x] = niv;
	for (const int& y : G[x])
    {
        if ( y == t[x] ) continue;
        if ( index[y]==0) // muchie de arbore
        {
            t[y] = x;
            st.push({x,y});
            DF(y, niv + 1);
            L[x] = min(L[x], L[y]);
            if(L[y]>=index[x]) Extract(x,y);
        }
        else L[x] = min(L[x], index[y]); // muchie de intoarcere

    }
}
void PuncteArticulatie()
{
	if ( nr > 1 ) p[root] = true;   // rad e punct de articulatie daca din ea pleaca cel putin doua muchii de arbore
	for (int i = 1; i <= n; i++ )
    {
		if ( i == root || t[i] == root)  continue;
        if ( L[i] >= index[t[i]] ) p[t[i]] = true;
    }
    for (int i = 1; i <= n; i++ )
        if ( p[i]) fo<<i<<" ";
}
void Write()
{
fo<<sol<<'\n';
for (int i = 1; i <= sol; ++i,fo<<'\n')
    for (auto y : comp[i])
            fo<<y<<" ";
}

int main()
{
	Read();
	root = 1;
	DF(root, 1);
	Write();
	//PuncteArticulatie();
	return 0;
}