Cod sursa(job #661973)

Utilizator marinMari n marin Data 15 ianuarie 2012 17:17:58
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define DIM 100010

using namespace std;

struct muchie {
	int a;
	int b;
};

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

nod *V[DIM], *q;

vector<int> L[DIM];
int N, M, X, Y, i, j, comp, s;
muchie r;

int Uz[DIM], Niv[DIM];

muchie S[2*DIM];

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

void dfs(int x, int t, int niv, int &nivMin) {
	Niv[x] = nivMin = niv;
	Uz[x] = 1;
	nod *q;
	for (q = V[x];q!=NULL;q = q->adr) {
		if (q->inf == t)
			continue;
		if (Uz[q->inf] == 0) {
			S[++s].a = x;
			S[s].b = q->inf;
			int nivMinFiu = DIM;
			dfs(q->inf, x, niv+1, nivMinFiu);
			nivMin = minim(nivMin, nivMinFiu);
			
			if (nivMinFiu >= niv) {
				++comp;
				do {
					r = S[s--];
					L[comp].push_back(r.a);
					L[comp].push_back(r.b);
				} while (!( r.a == x && r.b == q->inf  ));
			}
			
		} else {
			nivMin = minim(nivMin, Niv[q->inf]);
		}
	}
	Niv[x] = nivMin;
}


int main() {
	FILE *f = fopen("biconex.in","r");
	FILE *g = fopen("biconex.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;
		q = new nod;
		q->inf = X;
		q->adr = V[Y];
		V[Y] = q;
	}
	fclose(f);
	int nivMinFiu;
	dfs(1, 1, 1, nivMinFiu);
	fprintf(g,"%d\n",comp);
	for (i=1;i<=comp;i++) {
		L[i].push_back(DIM+1);
		sort(L[i].begin(), L[i].end());
		for (j=0;j<L[i].size()-1;j++)
			if (L[i][j] != L[i][j+1])
				fprintf(g,"%d ",L[i][j]);
		
		fprintf(g,"\n");
	}
	return 0;
}