Cod sursa(job #595289)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 11 iunie 2011 20:04:43
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
#include <iostream>
#include <fstream>
#include <vector>

#define x first
#define y second

using namespace std;

vector <int> G[100005], BC[100005];
vector < pair <int, int> > Edge;
int N, Level[100005], LowestL[100005], NBC;
bool Component[100005];

void Read ()
{
	ifstream fin ("biconex.in");
	int i, M, X, Y;
	fin >> N >> M;
	for (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");
    int i, j;
    fout << NBC << "\n";
    for (i=0; i<NBC; ++i)
    {
        for (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)
{
    int i, x, y;
    for (i=1; i<=N; ++i)
    {
        Component[i]=false;
    }
    Component[X]=true;
    Component[Y]=true;
    x=Edge[Edge.size ()-1].x;
    y=Edge[Edge.size ()-1].y;
    while ((x!=X) || (y!=Y))
    {
        Component[x]=true;
        Component[y]=true;
        Edge.pop_back ();
        x=Edge[Edge.size ()-1].x;
        y=Edge[Edge.size ()-1].y;
    }
    Edge.pop_back ();
    for (i=1; i<=N; ++i)
    {
        if (Component[i]==true)
        {
            BC[NBC].push_back (i);
        }
    }
    NBC++;
}

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

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