Cod sursa(job #603125)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 14 iulie 2011 17:26:18
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>
#include <algorithm>

#define x first
#define y second
#define NMax 100005

using namespace std;

vector <int> G[NMax];
stack < pair <int, int> > Edge;
vector < vector <int> > BC;
int N, Level[NMax], LowestL[NMax];

void Read ()
{
	ifstream fin ("biconex.in");
	int M, X, Y;
	fin >> N >> M;
	for (int i=1; i<=N; ++i)
	{
	    Level[i]=-1;
	}
	for (; M>0; --M)
	{
		fin >> X >> Y;
		G[X].push_back (Y);
		G[Y].push_back (X);
	}
	fin.close ();
}

void Type ()
{
    ofstream fout ("biconex.out");
    fout << BC.size () << "\n";
    for (unsigned i=0; i<BC.size(); ++i)
    {
        sort(BC[i].begin(), BC[i].end());
        BC[i].erase(unique(BC[i].begin(), BC[i].end()), BC[i].end());
        for (unsigned j=0; j<BC[i].size(); ++j)
        {
            fout << BC[i][j] << " ";
        }
        fout << "\n";
    }
    fout.close ();
}

inline int Min (int a, int b)
{
	if (a<b)
	{
		return a;
	}
	return b;
}

inline int Max (int a, int b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}

void DetBC (int X, int Y)
{
    vector <int> Component;
    int cx, cy;
    do
    {
        cx=Edge.top ().x;
        cy=Edge.top ().y;
        Edge.pop ();
        Component.push_back (cx);
        Component.push_back (cy);
    }
    while (cx!=X || cy!=Y);
    BC.push_back (Component);
}

void DFS (int X, int F, int L)
{
	vector <int> :: iterator V;
	LowestL[X]=Level[X]=L;
	for (V=G[X].begin (); V!=G[X].end (); ++V)
	{
		if (*V==F)
		{
		    continue;
		}
        if (Level[*V]==-1)
        {
            Edge.push (make_pair (X, *V));
            DFS (*V, X, L+1);
            LowestL[X]=Min (LowestL[X], LowestL[*V]);
            if (LowestL[*V]>=Level[X])
            {
                DetBC (X, *V);
            }
        }
        else
        {
            LowestL[X]=Min (LowestL[X], Level[*V]);
        }
	}
}

int main ()
{
	Read ();
	DFS (1, 0, 0);
	Type ();
	return 0;
}