Cod sursa(job #2198720)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 25 aprilie 2018 10:38:40
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define pii pair<int, int>
#define mk make_pair
#define MAX 100005
using namespace std;

int n, m, x, y;
int low[MAX], d[MAX];
vector<int> l[MAX], c;
vector<vector<int> > bic;
stack<pii> edges;

void biconex(int x, int p, int depth) {
	d[x] = low[x] = depth;

	for(int i = 0; i < l[x].size(); ++i) {
		if(l[x][i] == p)
			continue;
		if(!d[l[x][i]]) {
			edges.push(mk(x, l[x][i]));
			biconex(l[x][i], x, depth + 1);
			low[x] = min(low[x], low[l[x][i]]);
			if(depth <= low[l[x][i]]) {
				int p1, p2;
				c.clear();
				do {
					p1 = edges.top().first;
					p2 = edges.top().second;
					edges.pop();
					c.push_back(p2);
				} while(p1 != x || p2 != l[x][i]);
				c.push_back(p1);
				bic.push_back(c);
			}
		}
		else
			low[x] = min(low[x], d[l[x][i]]);
	}
}

int main() {
	ifstream f("biconex.in");
	ofstream g("biconex.out");

	f >> n >> m;
	for(int i = 0; i < m; ++i) {
		f >> x >> y;
		l[x].push_back(y);
		l[y].push_back(x);
	}

	for(int i = 1; i <= n; ++i)
		if(!low[i])
			biconex(i, 0, 1);

	g << bic.size() << "\n";
	for(int i = 0; i < bic.size(); ++i) {
		sort(bic[i].begin(), bic[i].end());
		for(int j = 0; j < bic[i].size(); ++j)
			g << bic[i][j] << " ";
		g << "\n";
	}
	return 0;
}