Cod sursa(job #915989)

Utilizator crushackPopescu Silviu crushack Data 15 martie 2013 17:57:39
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
#define NMax 100010
using namespace std;

const char IN[]="biconex.in",OUT[]="biconex.out";

int N,M;
vector<int> ad[NMax];
vector<vector<int> > C;

void make(int x,int y,stack<pair<int,int> > &st){
	pair<int,int> p;
	p.first=p.second=0;
	vector<int> vec;
	while (p.first!=x || p.second!=y){
		p=st.top();st.pop();
		vec.push_back(p.first);
		vec.push_back(p.second);
	}
	C.push_back(vec);
}

void dfs(int x,int p=-1,int lv=0)
{
	static stack<pair<int,int> > st;
	static int idx[NMax],low[NMax];
	static bool b[NMax];

	if (b[x]) return;
	int i,ct=0;
	idx[x]=low[x]=lv;
	b[x]=true;

	for (i=0;i<(int)ad[x].size();++i)
	{
		if (ad[x][i]==p) continue;
		if (!b[ad[x][i]])
		{
			st.push(make_pair(x,ad[x][i]));
			dfs(ad[x][i],x,lv+1);
			low[x]=min(low[x],low[ad[x][i]]);
			if (low[ad[x][i]]>=idx[x])
				make(x,ad[x][i],st);
		}
		else
			low[x]=min(low[x],idx[ad[x][i]]);
	}

}

int main()
{
	int i,j,x,y;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&M);
	for (i=1;i<=M;++i)
	{
		scanf("%d%d",&x,&y);
		ad[x].push_back(y);
		ad[y].push_back(x);
	}
	fclose(stdin);

	dfs(1);

	freopen(OUT,"w",stdout);
	printf("%d\n",C.size());
	for (i=0;i<(int)C.size();++i){
		sort(C[i].begin(),C[i].end());
		C[i].erase(unique(C[i].begin(),C[i].end()),C[i].end());
		for (j=0;j<(int)C[i].size();++j)
			printf("%d ",C[i][j]);
		printf("\n");
	}
	fclose(stdout);
	return 0;
}