Cod sursa(job #1978878)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 9 mai 2017 00:31:06
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <stack>
using namespace std;

#ifdef INFOARENA
#define ProblemName "biconex"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

#define MAXN 100010
vector<int> G[MAXN];
vector<int> ccmp[MAXN];
stack<int> S;
int ccnr = 0;
int dpth[MAXN], lowp[MAXN];

void makeComp(int root, int lookfor) {
	while (!S.empty()) {
		int t = S.top();
		ccmp[ccnr].push_back(t);
		S.pop();
		if (t == lookfor) break;
	}
	ccmp[ccnr].push_back(root);
	++ccnr;
}

void DFS(int nod, int parent, int level) {
	dpth[nod] = level;
	lowp[nod] = dpth[nod];
	S.push(nod);
	for (const auto &it : G[nod]) {
		if (dpth[it] >= 0) {
			if (it != parent)
				lowp[nod] = min(lowp[nod], dpth[it]);
			continue;
		}
		DFS(it, nod, level + 1);
		lowp[nod] = min(lowp[nod], lowp[it]);
		if (lowp[it] >= dpth[nod])
			makeComp(nod, it);
	}
}

void printComps() {
	printf("%d\n", ccnr);
	for (int i = 0; i < ccnr; ++i) {
		for (const auto &j : ccmp[i])
			printf("%d ", j + 1);
		putchar('\n');
	}
}

void input() {
	int N, M;
	scanf("%d%d", &N, &M);
	for (int i = 0; i < M; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		--a, --b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OuFile, "w", stdout));
	memset(dpth, 0xFF, sizeof(dpth));
	input();
	DFS(0, -1, 0);
	printComps();
	return 0;
}