Cod sursa(job #296136)

Utilizator raduzerRadu Zernoveanu raduzer Data 4 aprilie 2009 12:22:59
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 100010;
const int nod_s = 1;
const int INF = 0x3f3f3f3f;

int n, m, z, k, sol;
int niv[MAX_N], f[MAX_N], par[MAX_N], c[MAX_N], scris[MAX_N], noduri[MAX_N];
int st1[MAX_N], st2[MAX_N];
vector <int> v[MAX_N], s[MAX_N];

void checkMin(int &a, int b)
{
	if (a > b) a = b;
}

void df(int nod)
{
	f[nod] = 1;
	c[nod] = niv[nod];
	
	for (int i = 0; i < v[nod].size(); ++i)
	{
		int fiu = v[nod][i];
		
		if (!f[fiu])
		{
			par[fiu] = nod;
			niv[fiu] = niv[nod] + 1;
			

			st1[++k] = nod;
			st2[k] = fiu;
			
			df(fiu);
			checkMin(c[nod], c[fiu]);
			
			if (c[fiu] >= niv[nod])
			{
				++sol;
//				printf("%d\n", sol);
				while (!(st1[k] == nod && st2[k] == fiu)) 
				{
					s[sol].push_back(st1[k]);
					s[sol].push_back(st2[k]);
					--k;
				}
				s[sol].push_back(st1[k]);
				s[sol].push_back(st2[k]);
				--k;
			}
		}
		else 
		if (par[nod] != fiu && niv[fiu] < niv[nod])
		{
			checkMin(c[nod], niv[fiu]);
			st1[++k] = nod;
			st2[k] = fiu;
		}
	}
}

int main()
{
	int i, x, y;
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	
	for (i = 1; i <= m; ++i)
	{
		scanf("%d %d", &x, &y);
		
		v[x].push_back(y);
		v[y].push_back(x);
	}

	niv[nod_s] = 1;
	df(nod_s);

	printf("%d\n", sol);
	for (i = 1; i <= sol; ++i)
	{
		sort(s[i].begin(), s[i].end());
		s[i].push_back(INF);
		for (int j = 0; j < s[i].size() - 1; ++j)
			if (s[i][j] != s[i][j + 1]) printf("%d ", s[i][j]);
		printf("\n");
	}
}