Cod sursa(job #2082932)

Utilizator ice_creamIce Cream ice_cream Data 6 decembrie 2017 21:48:06
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 100000 + 1;

int n, top;
int stiva[NMAX];
int nivel[NMAX];
vector <int> graf[NMAX];
vector < vector <int> > sol;

void citeste() {
	int m, a, b;
	f >> n >> m;

	while (m--) {
		f >> a >> b;
		graf[a].push_back(b);
		graf[b].push_back(a);
	}
}

int muchiiDeIntoarcere(int nod, int tata) {
	nivel[nod] = nivel[tata] + 1;
	stiva[++top] = nod;
	int minim = nivel[nod];


	int l = graf[nod].size();
	for (int i = 0; i < l; i++) {
		int fiu = graf[nod][i];

		if (fiu == tata) continue;
		if (nivel[fiu]) {
			minim = min(minim, nivel[fiu]);
			continue;
		}

		int x = top;
		int niv = muchiiDeIntoarcere(fiu, nod);
		if (niv >= nivel[nod]) {
			vector <int> comp;
			comp.push_back(nod);
			while (top != x) {
				comp.push_back(stiva[top]);
				top--;
			}
			sol.push_back(comp);
		}
		minim = min(niv, minim);
	}

	return minim;
}
 
void rezolva() {
	muchiiDeIntoarcere(1, 0);
}

void scrie() {
	int l = sol.size();
	g << l << '\n';
	for (int i = 0; i < l; i++) {
		int k = sol[i].size();
		for (int j = 0; j < k; j++)
			g << sol[i][j] << ' ';
		g << '\n';
	}
}

int main() {
	citeste();
	rezolva();
	scrie();
}