Cod sursa(job #813167)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 14 noiembrie 2012 23:20:48
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
#define nmax 100010
#define f first
#define s second

vector <int> g[nmax], sol[nmax];
stack <pair <int, int> > s;
int n, m, lev[nmax], levacc[nmax], cnt, u[nmax], p[nmax];

void df (int nod, int t) {
	levacc[nod] = lev[nod];
	u[nod] = 1;
	int i, v, x;
	for (i = 0; i < g[nod].size(); i++) {
		v = g[nod][i];
		if (v != t) {
			if (u[v]) {
				if (lev[v] < lev[nod])
					s.push (make_pair (nod, v));
				levacc[nod] = min (levacc[nod], lev[v]);
			} else {
				lev[v] = lev[nod] + 1;
				s.push (make_pair (nod, v));
				df (v, nod);
				if (levacc[v] >= lev[nod]) {
					cnt++;
					int ok = 0;
					while (1) {
						x = s.top().first;
						if (p[x] != cnt) {
							sol[cnt].push_back(x);
							p[x] = cnt;
						}
						x = s.top().second;
						if (p[x] != cnt) {
							sol[cnt].push_back(x);
							p[x] = cnt;
						}
						if (s.top() == make_pair (nod, v)) break;
						s.pop();
						ok = 1;
					}
					s.pop();
				}
				levacc[nod] = min(levacc[nod], levacc[v]);
			}
		}
	}
}

int main()
{
	freopen ("biconex.in", "r", stdin);
	freopen ("biconex.out", "w", stdout);
	scanf ("%d %d", &n, &m);
	int i, x, y, j;
	for (i = 1; i <= m; i++)
	{
		scanf ("%d %d", &x, &y);
		g[x].push_back (y);
		g[y].push_back (x);
	}
	lev[1] = 1;
	df (1, 0);
	printf ("%d\n", cnt);
	for (i = 1; i <= cnt; i++)
	{
		for (j = 0; j < sol[i].size(); j++) printf ("%d ",sol[i][j]);
		printf("\n");
	}
}