Cod sursa(job #833322)

Utilizator marius135Dumitran Adrian Marius marius135 Data 12 decembrie 2012 12:46:24
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>

using namespace std;
#define maxn 100100

stack <int> stiva;
vector <int> vec[maxn];
vector <int> comp[maxn];
int N, M, nr = 0;
int sel[maxn];
int tata[maxn];


int df(int nod, int h) {
	
	stiva.push(nod);
	sel[nod] = h;
	for( size_t i = 0; i < vec[nod].size(); ++i) {
		int val;
		if( vec[nod][i] == tata[nod] ) continue;
		if( sel[ vec[nod][i]] == 0)  {
			tata[vec[nod][i]] = nod;
			df(vec[nod][i], h + 1);
			if( sel[vec[nod][i]] >= h ) {
				while( stiva.top() != nod) {
			
					comp[nr].push_back(stiva.top());
					stiva.pop();
				}
				comp[nr].push_back(stiva.top());
				sort(comp[nr].begin(), comp[nr].end());
				nr++;
			}
			
		}
		
		val = sel[vec[nod][i]];
		if( sel[nod] > val)
			sel[nod] = val;
	}
	return sel[nod];
		
}

int main() {
	
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	
	scanf("%d %d", &N, &M);
	
	for( int i = 1; i <= M; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	 
	for( int i = 1; i <= N; ++i) {
		if( sel[i] == 0) 
			df(i, 1);
	}

	cout<< nr<<endl;
	for( int j = 0; j < nr; ++j) {
		for( size_t i = 0; i < comp[j].size(); ++i)
			cout<< comp[j][i]<<" ";
		cout<<endl;
	}
	
	
	return 0;
}