Cod sursa(job #475521)

Utilizator robigiirimias robert robigi Data 7 august 2010 11:06:40
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
// Componente biconexe.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"
#include <vector>
#include <algorithm>

using namespace std;

FILE *f=fopen("biconex.in", "r");
FILE *g=fopen("biconex.out", "w");

typedef struct nod
{
	int x;
	struct nod *adr;
};

nod *l[100001];

int n, m, nr;
int dfn[100001], low[100001];
int cds[100001];
int cdf[100001];
int st;
int cv;

vector <vector<int>> c;


void add(int x, int y)
{
	nod *p=new nod;
	p->x=y;
	p->adr=l[x];
	l[x]=p;
}


void read()
{
	fscanf(f, "%d%d", &n, &m);
	for (int i=1; i<=m; ++i)
	{
		int x, y;
		fscanf(f, "%d%d", &x, &y);
		add(x, y);
		add(y, x);
	}
}


void init()
{
	for (int i=1; i<=n; ++i)
		dfn[i]=low[i]=-1;
	cds[1]=-1;
	cdf[1]=1;
}


int minim(int x, int y)
{
	if (x<y) return x;
	return y;
}


void afisare(int x, int u)
{
	vector <int> con;
	do
	{
		con.push_back(cds[st]);
		con.push_back(cdf[st--]);
	}while (cds[st+1]!=u || cdf[st+1]!=x);
	cv++;
	c.push_back(con);
}


void biconex (int u, int tu)
{
	int x;
	dfn[u]=low[u]=++nr;
	nod *p=l[u];
	while (p!=NULL)
	{
		x=p->x;
		if (x!=tu && dfn[x]<dfn[u])
		{
			cds[++st]=u;
			cdf[st]=x;
		}
		if (dfn[x]==-1)
		{
			biconex(x, u);
			low[u]=minim(low[u], low[x]);
			if (low[x]>=dfn[u])
			{
				afisare(x, u);
			}
		}	
		else
		{
			if (x!=tu)
				low[u]=minim(low[u], dfn[x]);
		}
		p=p->adr;
	}
}



int main()
{
	read();
	init();
	biconex(1, -1);
	fprintf(g, "%d\n", cv);
	for (size_t i=0; i<c.size(); ++i)
	{
		sort(c[i].begin(), c[i].end());
		for (size_t j = 0; j < c[i].size(); ++ j) 

		{
			if (j==0)
				fprintf(g, "%d ", c[i][j]);
			else
			{
				while (c[i][j]==c[i][j-1]) j++;
				if (j<c[i].size) fprintf(g, "%d ", c[i][j]);
			}
		}
		fprintf(g, "\n");
	}
	return 0;
}