Cod sursa(job #470665)

Utilizator TabaraTabara Mihai Tabara Data 15 iulie 2010 10:47:26
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

const int NMAX = 100005;
const int ALB = 0;
const int NEGRU = 1;

const char in[] = "ctc.in";
const char out[] = "ctc.out";

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

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

PNOD L[NMAX];
int N, M, level, nrsol;
int color[NMAX], l[NMAX], niv[NMAX];

stack<int> st;
vector<int> t;

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

void DF(int nod)
{
	PNOD p;
	int q;
	size_t j;

	color[nod] = NEGRU;
	niv[nod] = ++level;
	l[nod] = level;
	st.push(nod);

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

	if (l[nod] == niv[nod])
	{
		++nrsol;
		t.clear();
		while (1)
		{
			t.push_back(q = st.top());
			color[q] = ALB;
			st.pop();
			if (q == nod) break;
		}
		for (j = 0; j < t.size(); ++j)
			printf("%d ", t[j]);
		printf("\n");
	}
}

int main(int argc, char **argv)
{
	freopen(in, "r", stdin);
	freopen(out, "w", stdout);

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

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

	return 0;
}