Cod sursa(job #662013)

Utilizator marinMari n marin Data 15 ianuarie 2012 18:08:36
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <stdio.h>
#include <vector>
#define DIM 100010

using namespace std;

struct nod {
	int inf;
	nod *adr;
};

int minim(int a, int b) {
	return a<b ? a : b;
}

int inStack[DIM];
vector<int> L[DIM];
nod *V[DIM], *q;
int N, M, i, j, X, Y, comp, s, niv;
int Niv[DIM], Min[DIM], S[DIM];

void tarjan(int x) {
	niv ++;
	Niv[x] = Min[x] = niv;
	S[++s] = x;
	inStack[x] = 1;
	for (nod *q = V[x]; q != NULL; q = q->adr) {
		if (Niv[q->inf] == 0) {
			tarjan(q->inf);
			Min[x] = minim(Min[x], Min[q->inf]);
		} else
			if (inStack[q->inf])
				Min[x] = minim(Min[x], Min[q->inf]);
	}
	if (Min[x] == Niv[x]) {
		comp++;
		do {
			L[comp].push_back(S[s--]);
			inStack[S[s+1]] = 0;
		} while (S[s+1]!=x);
	}
}

int main() {
	FILE *f = fopen("ctc.in", "r");
	FILE *g = fopen("ctc.out", "w");
	fscanf(f,"%d %d", &N, &M);
	for (i=1;i<=M;i++) {
		fscanf(f,"%d %d",&X, &Y);
		q = new nod;
		q->inf = Y;
		q->adr = V[X];
		V[X] = q;
	}
	fclose(f);
	for (i=1;i<=N;i++)
		if (Niv[i] == 0)
			tarjan(i);
	fprintf(g,"%d\n",comp);
	for (i=1;i<=comp;i++) {
		for (j=0;j<L[i].size();j++)
			fprintf(g,"%d ",L[i][j]);
		fprintf(g,"\n");
	}
	return 0;
}