Cod sursa(job #1740706)

Utilizator howsiweiHow Si Wei howsiwei Data 12 august 2016 07:42:00
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;

const int nil = -1;

vector<vector<int>> adjl;
vector<int> depth;
vector<int> low;
stack<int> t;
vector<vector<int>> bccs;

void dfs(int u, int p, int d) {
	low[u] = depth[u] = d;
	t.push(u);
	for (auto v: adjl[u]) if (v != p) {
		if (low[v] == nil) {
			dfs(v, u, d+1);
			if (low[v] >= d) {
				vector<int> bcc;
				int top;
				do {
					top = t.top();
					t.pop();
					bcc.push_back(top);
				} while (top != v);
				bcc.push_back(u);
				bccs.push_back(bcc);
			} else low[u] = min(low[u], low[v]);
		} else low[u] = min(low[u], depth[v]);
	}
}

int main() {
	ios::sync_with_stdio(false);
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	int n, m;
	cin >> n >> m;
	adjl.assign(n, {});
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		adjl[u].push_back(v);
		adjl[v].push_back(u);
	}
	low.assign(n, nil);
	dfs(0, nil, 0);
	printf("%d\n", bccs.size());
	for (auto& bcc: bccs) {
		for (auto u: bcc) {
			printf("%d ", u+1);
		}
		printf("\n");
	}
	return 0;
}