Cod sursa(job #524598)

Utilizator cristiprgPrigoana Cristian cristiprg Data 22 ianuarie 2011 13:56:48
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <cstdio>
#include <stack>
#include <bitset>
#include <vector>
using namespace std;
#define pb push_back
#define mp make_pair
#define IT vector<int>::iterator
#define DIM 100005

int n, m, D[DIM], low_point[DIM], Count;
vector<int> G[DIM];
vector<pair <int, int > >ANS[DIM];
stack<pair<int, int> > S;
bitset<DIM>v;

inline int min(const int &a, const int &b)
{
	return a<b?a:b;
}

void afis()
{
	for (int i = 1; i <= n; ++i)
	{
		printf("%d: ", i);
		for (IT it = G[i].begin(); it != G[i].end(); ++it)
			printf("%d ", *it);
		printf("\n");
	}
}	

void read(void)
{
	FILE *f = fopen("biconex.in", "r");
	fscanf(f, "%d%d", &n, &m);
	for (int i = 1, x, y; i <= m; ++i)
	{
		fscanf(f, "%d%d", &x, &y);
		G[x].pb(y);
		G[y].pb(x);
	}
	fclose(f);
	
}

void componenta(int x, int y)
{
	int i, j;
	++Count;
//	printf("comp %d:\n", Count);
	do
	{
		i = (S.top()).first;
		j = (S.top()).second;
		S.pop();
//		printf("%d %d\n", i, j);
		ANS[Count].pb(mp(i, j));
	}while (i != x && j != y);
}

void DFS(int i, int depth)
{
	D[i] = depth;
	v[i] = 1;
	low_point[i] = depth;
	for (IT it = G[i].begin(); it != G[i].end(); ++it)
	{
		if (!v[*it])
		{
			S.push(mp(i, *it));
			DFS(*it, depth+1);
			low_point[i] = min(low_point[i], low_point[*it]);
			if (low_point[*it] >= D[i]) // i -> punct de articulatie
				componenta(i, *it);
		}
		else
			low_point[i] = min(low_point[i], D[*it]);
	}	
}

void write(void)
{
	v.set();
	FILE *f = fopen("biconex.out", "w");
	fprintf(f, "%d\n", Count);
	for (int i = 1; i <= Count; ++i)
	{
		for (vector<pair<int, int> >::iterator it = ANS[i].begin(); it != ANS[i].end(); ++it)
		{
			if (v[it->first] == 1)	fprintf(f, "%d ", it->first), v[it->first] = 0;
			if (v[it->second] == 1)	fprintf(f, "%d ", it->second),v[it->second] = 0;
		}
		fprintf(f, "\n");
		v.set();
	}
	fclose(f);
}

int main(void)
{
	read();
	DFS(1, 0);
	write();
	return 0;
}