Cod sursa(job #437244)

Utilizator ooctavTuchila Octavian ooctav Data 9 aprilie 2010 15:30:06
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#define pb push_back
#define mp make_pair
using namespace std;
const int NMAX = 100010;

int N, M;
vector<int> G[NMAX];
int dfn[NMAX], low[NMAX];
stack< pair<int, int> > st;
vector< vector<int> > biconex;

/*void write()
{
	for(int i = 1 ; i <= M ; i++)
	{
		for(int k = 0 ; k < (int)G[i].size() ; k++)
			printf("%d ", G[i][k]);
		printf("\n");
	}
	
	for(int i = 1 ; i <= N ; i++)
		printf("%d ", dfn[i]);
	printf("\n");
	for(int i = 1 ; i <= N ; i++)
		printf("%d ", low[i]);
	
	printf("\n\n\n");
}*/

void citire()
{
	int x, y;
	scanf("%d%d", &N, &M);
	for(int i = 1 ; i <= M ; i++)
	{
		scanf("%d%d", &x, &y);
		G[x].pb(y);
		G[y].pb(x);
	}
	
}

void introduc(int x, int y)
{
	vector<int> cb;
	pair<int, int> a;
	
	do
	{
		a = st.top();
		cb.pb(a.first);
		cb.pb(a.second);
		st.pop();
	}while(x != a.first || y != a.second);
	
	biconex.pb(cb);
}

void DFS(int nod, int tata, int nivel)
{
	vector<int> :: iterator it;
	dfn[nod] = low[nod] = nivel;
	
	for(it = G[nod].begin() ; it != G[nod].end() ; ++it)
		if(*it != tata)
			if(dfn[*it] == -1)
			{
				st.push(mp(*it, nod));
				DFS(*it, nod, nivel+1);
				low[nod] = min(low[nod], low[*it]);
				if(low[*it] >= dfn[nod])
					introduc(*it, nod);
			}
			else
				low[nod] = min(low[nod], dfn[*it]);//merge si min(low[nod], low[*it])
}

void scriere()
{	
	vector<int> :: iterator dim;
	printf("%d\n",biconex.size());
	sort(biconex.begin(), biconex.end());
	for(int i = 0 ; i < (int)biconex.size() ; ++i)
	{
		//sort(biconex[i].begin(), biconex[i].end());
		dim = unique(biconex[i].begin(), biconex[i].end());
		biconex[i].resize(dim - biconex[i].begin());
		for(int k = 0 ; k < (int)biconex[i].size() ; ++k)
			printf("%d ",biconex[i][k]);
		printf("\n");
	}
}

int main()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	citire();
	memset(dfn, -1, NMAX);
	DFS(1, 0, 1);
	//write();
	scriere();
	
	return 0;
}