Cod sursa(job #3192608)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 13 ianuarie 2024 00:53:51
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.28 kb
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
const int NR = 100005;
ofstream out("biconex.out");
vector < int > v[NR];
vector < pair < int, int > > st;
int n, m, lvl[NR], lowest[NR];
vector < vector < int > > ans;
void make_cb(int x, int y) {
	vector < int > c;
	int cx, cy;
	do {
		cx = st.back().first;
		cy = st.back().second;
		st.pop_back();
		c.push_back(cx), c.push_back(cy);
	} while (!(cx == x && cy == y));
	ans.push_back(c);
}
void dfs(int nod, int father) {
	vector < int > ::iterator it;
	lowest[nod] = lvl[nod];
	for (it = v[nod].begin(); it != v[nod].end(); ++it) {
		if (*it == father)    continue;
		if (!lvl[*it]) {
			lvl[*it] = lvl[nod] + 1;
			st.push_back(mp(nod, *it));
			dfs(*it, nod);
			lowest[nod] = min(lowest[nod], lowest[*it]);
			if (lowest[*it] == lvl[nod])    make_cb(nod, *it);
		}
		else {
			lowest[nod] = min(lowest[nod], lvl[*it]);
		}
	}

}


class InParser {
private:
	FILE* fin;
	char* buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int& n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		}
		else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long& n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		}
		else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};

int main() {
	InParser in("biconex.in");
	int x, y, a, b;
	in >> n >> m;
	lvl[1] = 1;
	while (m--) {
		in >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1, 0);
	a = ans.size();
	out << a << '\n';
	for (size_t i = 0; i < a; ++i, out << '\n') {
		sort(ans[i].begin(), ans[i].end());
		ans[i].erase(unique(ans[i].begin(), ans[i].end()), ans[i].end());
		b = ans[i].size();
		for (size_t j = 0; j < b; ++j) out << ans[i][j] << ' ';
	}
}