Cod sursa(job #1539161)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 30 noiembrie 2015 13:08:55
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <cstdio>
#include <vector>
#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;

vector <vector <int> > BCC;

int N;

void biconex(int u, int v) {
	vector <int> tmp;
	do {
		ss--;
		tmp.emplace_back(st[2 * ss]);
		tmp.emplace_back(st[2 * ss + 1]);
	} while (st[2 * ss] != u || st[2 * ss + 1] != v);
	sort(tmp.begin(), tmp.end());
	tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
	BCC.emplace_back(tmp);
}

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);
	}
	fclose(stdin);

	dfs(0);

	printf("%lu\n", BCC.size());
	for (auto v : BCC) {
		for (auto q : v) {
			printf("%d ", 1 + q);
		}
		putchar('\n');
	}
	fclose(stdout);
	return 0;
}