Cod sursa(job #968987)

Utilizator dropsdrop source drops Data 3 iulie 2013 11:11:07
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <ctime>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream ff("biconex.in");
ofstream gg("biconex.out");
#define max 100001
vector<int> vv[max];
vector<set<int> > ll;
bool ww[max];
struct per{ int x,y; per(int x0=0,int y0=0){x=x0;y=y0;} }cc[max];
int n, m, zz[max], mm[max], p;

void cmp(int x,int y){
	int a, b;
	set<int> ss;
	do{
		a=cc[p].x; b=cc[p].y;
		ss.insert(a); ss.insert(b);
		p--;
	} while(a!=x || b!=y);
	ll.push_back(ss);
}

void dfs(int f,int t,int k){
	int u;
	zz[f]=mm[f]=k;
	ww[f]=1;
	for(int i=0;i<(int)vv[f].size();i++){
		u=vv[f][i];
		if(u==t) continue;
		if(!ww[u]){
			cc[++p]=per(f,u);
			dfs(u, f, k+1);
			mm[f]=min(mm[f], mm[u]);
			if(mm[u]>=zz[f])
				cmp(f, u);
		} else
			mm[f]=min(mm[f], zz[u]);
	}
}
 
int main(){
	int x, y;
	ff >> n >> m;
	for(int i=0;i<m;i++){
		ff >> x >> y;
		vv[x].push_back(y);
		vv[y].push_back(x);
	}
	dfs(1,0,0);
	set<int>::iterator it;
	gg << ll.size() << "\n";
	for(int i=0;i<(int)ll.size();i++){
		it=ll[i].begin();
		while(it!=ll[i].end()){
			gg << *it << " ";
			it++;
		}
		gg << "\n";
	}
}