Cod sursa(job #470414)

Utilizator TabaraTabara Mihai Tabara Data 13 iulie 2010 18:25:09
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

#define ALB 0
#define GRI 1

using namespace std;

const int NMAX = 100005;
const char in[] = "ctc.in";
const char out[] = "ctc.out";

typedef struct nod {
	int vf;
	struct nod *next;
} *PNOD, NOD;

PNOD L[NMAX];

void Add(int i, int j)
{
	PNOD p = new NOD;
	p->vf = j;
	p->next = L[i];
	L[i] = p;
}

stack<int> st;
int level;
int l[NMAX], niv[NMAX], sel[NMAX], tata[NMAX];
int N, M, nrsol;

void DF(int);

template <class T>
T minx(T a, T b)
{
	return a < b ? a : b;
}

int main(void)
{
	freopen (in, "r", stdin);
	freopen(out, "w", stdout);

	scanf("%d%d", &N, &M);
	int i;
	size_t j;

	for ( ; M; --M)
	{
		scanf ("%d%d", &i, &j);
		Add(i, j);
	}
	printf("			\n");
	for (i = 1; i <= N; ++i)
		if (sel[i] == ALB)
			DF(i);
	fseek(stdout, 0, SEEK_SET);
	printf("%d", nrsol);

	return 0;
}
void DF(int nod)
{
	niv[nod] = ++level;
	l[nod] = level;
	sel[nod] = GRI;
	st.push(nod);

	PNOD p;
	int x;

	for (p = L[nod]; p; p = p->next)
	{
		if (sel[p->vf] == ALB)
		{
			DF(p->vf);
			l[nod] = minx(l[nod], l[p->vf]);
		}
		else
			l[nod] = minx(l[nod], niv[p->vf]);
	}

	if (l[nod] == niv[nod])
	{
		++nrsol;
		while(1)
		{
			x = st.top();
			printf("%d ", x);
			st.pop();
			if (x == nod) break;
		}
		printf("\n");
	}
}