Cod sursa(job #1222782)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 24 august 2014 13:06:41
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define MAX 100010

vector<int> Gr[MAX];
vector<vector<int> > Cbc;
stack<pair<int,int> > S;
pair<int,int> P;
bool Use[MAX];
int N, M, Idx[MAX], Low[MAX], idx;

void Dfs(int X) {
	int Y;
	Use[X] = 1;
	idx++;
	Idx[X] = Low[X] = idx;
	for (int i = 0; i < Gr[X].size(); i++) {
		Y = Gr[X][i];
		if (!Use[Y]) {
			S.push(make_pair(X,Y));
			Dfs(Y);
			Low[X] = min(Low[X], Low[Y]);
			if (Low[Y] >= Idx[X]) {
				Cbc.resize(Cbc.size()+1);
				do {
					P = S.top();
					S.pop();
					Cbc[Cbc.size()-1].push_back(P.second);
				} while (P.first != X || P.second != Y);
				Cbc[Cbc.size()-1].push_back(P.first);
			}
		} else {
			Low[X] = min(Low[X], Idx[Y]);
		}
	}
}

int main() {
	int X, Y;

	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &X, &Y);
		Gr[X].push_back(Y);
		Gr[Y].push_back(X);
	}
	
	Dfs(1);
		
	printf("%d\n", Cbc.size());
	for (int i = 0; i < Cbc.size(); i++, printf("\n"))
		for (int j = 0; j < Cbc[i].size(); j++) printf("%d ", Cbc[i][j]);

	return 0;
}