Cod sursa(job #1075572)

Utilizator TeOOOVoina Teodora TeOOO Data 9 ianuarie 2014 11:03:27
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
//Include
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
using namespace std;
FILE *in, *out;

//Constante
const int sz = (int)1e5+1;

//Definitii
#define pb push_back
#define edge pair<int, int>
#define mp make_pair
#define rock top

//Functii
void dfs(int node, int father, int level);
void biconex(edge stop);

//Variabile
int nodes, edges;
int depth[sz], minLevel[sz];

vector <int> graph[sz];
stack <edge> music;
vector< set<int> > answer;

//Main
int main()
{
	in = fopen("biconex.in", "rt");
	out = fopen("biconex.out", "wt");
	fscanf(in,"%d%d",&nodes, &edges);

	int rFrom, rTo;
	for(int i=1; i<=edges; ++i)
	{
		fscanf(in,"%d%d", &rFrom, &rTo);
		graph[rFrom].pb(rTo);
		graph[rTo].pb(rFrom);
	}
	dfs(1, -1, 1);
	fprintf(out,"%d\n", answer.size());

	vector< set<int> >::iterator it, end = answer.end();
	for(it=answer.begin(); it!=end; ++it)
	{
		set<int>::iterator sit, send = it->end();
		for(sit=it->begin(); sit!=send; ++sit)
			fprintf(out,"%d ", *sit);
		fprintf(out,"\n");
	}

	fclose(in);
	fclose(out);
	return 0;
}

void dfs(int node, int father, int level)
{
	depth[node] = minLevel[node] = level;
	vector<int>::iterator it, end = graph[node].end();

	for(it=graph[node].begin(); it!=end; ++it)
	{
		if(*it == father)
			continue;

		if(depth[*it])
		{
			minLevel[node] = min(minLevel[node], depth[*it]);
			continue;
		}
		music.push(mp(node, *it));
		dfs(*it, node, level+1);

		minLevel[node] = min(minLevel[node], minLevel[*it]);

		if(level <= minLevel[*it])
			biconex(mp(node, *it));
	}
}

void biconex(edge stop)
{
	set <int> temp;
	edge current;

	do
	{
		current = music.rock();
		music.pop();
		temp.insert(current.first);
		temp.insert(current.second);
	} while(current != stop);

	answer.pb(temp);
	temp.clear();
}