Cod sursa(job #1909258)

Utilizator Cudrici_CarinaCudrici Carina Cudrici_Carina Data 7 martie 2017 12:02:17
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 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,ind,sol;
bool p[MAX];     // p[i] == true daca i e pct. articulatie
int index[MAX];  // indexul 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

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)
{
L[x] = index[x] = ind++;
for (const int& y : G[x])
    if ( index[y]==0) // muchie de arbore
        {
            st.push({x,y});
            DF(y);
            L[x] = min(L[x], L[y]);
            if(L[y]>=index[x]) {  //p[x]=true; x este punct de articulatie
                                  //fo<<x<<" "<<y; muchia de la x la y este de articluatie
                                  Extract(x,y);}
        }
        else L[x] = min(L[x], index[y]); // muchie de intoarcere
}

void Write()
{
fo<<sol<<'\n';
for (int i = 1; i <= sol; ++i,fo<<'\n')
    for (auto y : comp[i])
            fo<<y<<" ";
}

int main()
{
	Read();
	DF(1);
	Write();

	return 0;
}