Cod sursa(job #937128)

Utilizator BitOneSAlexandru BitOne Data 9 aprilie 2013 21:17:59
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <set>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>

using namespace std;
typedef pair<int, int> pr;
const int NMAX = 100011;

int idx, countBC;
int dfsIdx[NMAX], lowIdx[NMAX];

vector<pr> Stack; 
vector<int> G[NMAX];
set<int> BC[NMAX];

inline int min(int x, int y) {return x <= y ? x : y;}
inline void DFS(int x)
{
	dfsIdx[x] = lowIdx[x] = ++idx;
	vector<int>::iterator it = G[x].begin(), iend = G[x].end();
	
	for(; it < iend; ++it)
	{
		if(!dfsIdx[*it])
		{
			Stack.push_back(pr(x, *it));
			DFS(*it);
			lowIdx[x] = min(lowIdx[x], lowIdx[*it]);
			if(lowIdx[*it] >= dfsIdx[x])
			{
				pr z, y(x, *it);
				do {
						z = Stack.back(); Stack.pop_back();
						BC[countBC].insert(z.first);
						BC[countBC].insert(z.second);					
					}while(y != z);
				++countBC;
			}
		}
		else lowIdx[x] = min(lowIdx[x], dfsIdx[*it]);
	}	
}

int main()
{
	int N, M, x, y, i;
	ifstream in("biconex.in");
	ofstream out("biconex.out");
	
	for(in >> N >> M; M; --M)
	{
		in >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	
	for(i = 1; i <= N; ++i)
	{
		if(!dfsIdx[i])
		{
			DFS(i);
		}
	}
	out << countBC << '\n';
	for(i = 0; i < countBC; ++i)
	{
		copy(BC[i].begin(), BC[i].end(), ostream_iterator<int>(out, " "));
		out << '\n';
	}
	
	return EXIT_SUCCESS;
}