Cod sursa(job #1539165)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 30 noiembrie 2015 13:18:02
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAX_N = 100000;
const int MAX_M = 200000;
const int NIL = -1;

struct cell {
	int v;
	int next;
};

cell l[2 * MAX_M];
int adj[MAX_N];

int dfn[MAX_N];
int nextIndex;

int st[2 * MAX_N];
int ss;

cell BCCbuff[2 * MAX_N];
int ptr;
int startBCC[2 * MAX_M];
int numBCC;

int N;

bool onStack[MAX_N];

void biconex(int u, int v) {
	do {
		ss--;
		onStack[st[2 * ss]] = 1;
		onStack[st[2 * ss + 1]] = 1;
	} while (st[2 * ss] != u || st[2 * ss + 1] != v);
	for (int i = N - 1; i >= 0; i--) {
		if (onStack[i]) {
			BCCbuff[ptr].v = i;
			BCCbuff[ptr].next = startBCC[numBCC];
			startBCC[numBCC] = ptr++;
			onStack[i] = 0;
		}
	}
	numBCC++;
}

int dfs(int u) {
	int v, minPtr, minPtrV;
	
	dfn[u] = minPtr = nextIndex++;

	for (int i = adj[u]; i != NIL; i = l[i].next) {
		v = l[i].v;
		if (dfn[v] == NIL) {
			st[2 * ss] = u;
			st[2 * ss + 1] = v;
			ss++;
			minPtrV = dfs(v);
			minPtr = min(minPtr, minPtrV);
			if (minPtrV >= dfn[u]) {
				biconex(u, v);
			}
		} else {
			minPtr = min(minPtr, dfn[v]);
		}
	}
	return minPtr;
}

void addEdge(int u, int v, int pos) {
	l[pos].v = v;
	l[pos].next = adj[u];
	adj[u] = pos;
}

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

	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; i++) {
		adj[i] = dfn[i] = NIL;
	}
	for (int i = 0; i < M; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		addEdge(u - 1, v - 1, 2 * i);
		addEdge(v - 1, u - 1, 2 * i + 1);
		startBCC[2 * i] = NIL;
		startBCC[2 * i + 1] = NIL;
	}
	fclose(stdin);

	dfs(0);

	printf("%d\n", numBCC);
	for (int i = 0; i < numBCC; i++) {
		for (int j = startBCC[i]; j != NIL; j = BCCbuff[j].next) {
			printf("%d ", 1 + BCCbuff[j].v);
		}
		putchar('\n');
	}
	fclose(stdout);
	return 0;
}