Cod sursa(job #1539169)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 30 noiembrie 2015 13:28:33
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

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

char buff[BUFFSIZE];
int pos = 0;

inline void PutChar(const char &c) {
	buff[pos++] = c;
	if (pos == BUFFSIZE) {
		fwrite(buff, 1, BUFFSIZE, stdout);
		pos = 0;
	}
}

inline void PrintInteger(int x) {
	char digs[8];
	int n = 0, q;
	do {
		q = x / 10;
		digs[n++] = x - q * 10 + '0';
		x = q;
	} while (x != 0);
	while (n--) {
		PutChar(digs[n]);
	}
}

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;

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 N, 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);

	PrintInteger(BCC.size());
	PutChar('\n');
	for (auto v : BCC) {
		for (auto q : v) {
			PrintInteger(1 + q);
			PutChar(' ');
		}
		PutChar('\n');
	}
	fwrite(buff, 1, pos, stdout);
	fclose(stdout);
	return 0;
}