Cod sursa(job #381417)

Utilizator blasterzMircea Dima blasterz Data 10 ianuarie 2010 16:10:24
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <set>
#define N 100005
#define mp make_pair

using namespace std;

struct nod
{
	int x;
	nod *n;
};

nod *a[N];
inline void add(int i, int j)
{
	nod *p = new nod;
	p->x = j;
	p->n = a[i];
	a[i] = p;
}


stack<pair<int, int> > st;

int n, m;
int dfn[N];
int low[N];

vector<vector<int> > sol;

void read()
{
	freopen("biconex.in","r",stdin);
	scanf("%d %d\n", &n, &m);
	
	int x, y;
	
	while(m--)
	{
		scanf("%d %d\n", &x, &y);
		add(x,y);
		add(y,x);
	}
}

void getBiconexComponent(int fn, int n)
{
	vector<int> x;
	int i, j;
	
	do
	{
		i = st.top().first;
		j = st.top().second;
		st.pop();
		x.push_back(i);
		x.push_back(j);
	}while(fn != i && n != j);
	
	sol.push_back(x);
	
	
}
void dfs(int n, int tn, int nr)
{
	dfn[n] = low[n] = nr;
	
	for(nod * i = a[n]; i ; i = i->n)
	{
		if(i->x == tn) continue;
		if(dfn[i->x] == -1)
		{
			st.push(mp(n, i->x));
			dfs(i->x, n, nr+1);
			low[n] = min(low[n], low[i->x]);
			
			if(low[i->x] >= dfn[n]) 
				getBiconexComponent(n, i->x);
		}
		else low[n] = min(low[n], dfn[i->x]);
	}
}

int main()
{
	read();
	memset(dfn, -1, sizeof(dfn));
	
	dfs(1, 0, 0);
	
	int i, j;
	
	freopen("biconex.out","w",stdout);
	printf("%d\n", sol.size());
	for(i = 0; i < sol.size(); ++i)
	{
		set<int> a(sol[i].begin(), sol[i].end());
		
		for(set<int>::iterator it = a.begin(); it != a.end(); ++it)
			printf("%d ", *it);
		printf("\n");
	}
	
	return 0;
}