Cod sursa(job #2656861)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 8 octombrie 2020 22:51:13
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <utility>

using namespace std;

vector<vector<int>> arcs;
vector<int> low, df;
vector<vector<int>> res;
stack<pair<int, int>> st;

int min(int x, int y) {
	return x < y ? x : y;
}


void add_to_sol(int x, int y) {
	vector<int> current_res;
	int tx = 0, ty = 0;
	while (tx != x || ty != y) {
		tx = st.top().first;
		ty = st.top().second;

		st.pop();
		current_res.push_back(tx);
		current_res.push_back(ty);
	}

	res.push_back(current_res);
}


void dfs(int x, int past_x, int stackSize) {
	df[x] = low[x] = stackSize;

	for(int i=0; i<arcs[x].size(); ++i)
		if (arcs[x][i] != past_x) {
			if (df[arcs[x][i]] == 0) {
				st.push(pair<int, int>(x, arcs[x][i]));
				dfs(arcs[x][i], x, stackSize + 1);
				low[x] = min(low[x], low[arcs[x][i]]);

				if (low[arcs[x][i]] >= df[x])
					add_to_sol(x, arcs[x][i]);
			} else
				low[x] = min(low[x], df[arcs[x][i]]);
		}
}


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

	int n, m, x, y;
	scanf("%d%d", &n, &m);
	arcs.resize(n+1);
	low.resize(n+1, 0);
	df.resize(n+1, 0);

	for(int i=0; i<m; ++i) {
		scanf("%d%d", &x, &y);
		arcs[x].push_back(y);
		arcs[y].push_back(x);

	}

	for(int i=1; i<=n; ++i) {
		if (! df[i])
			dfs(i, 0, 1);
	}

	printf("%d\n", res.size());
	for(int i=0; i<res.size(); ++i) {
        sort(res[i].begin(), res[i].end());
		for(int j=0; j<res[i].size(); ++j)
            if (j == 0 || res[i][j] != res[i][j-1])
                printf("%d ", res[i][j]);
		printf("\n");
	}

	return 0;
}