Cod sursa(job #1378769)

Utilizator abel1090Abel Putovits abel1090 Data 6 martie 2015 14:12:29
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
///BICONNECTED COMPONENTS
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <algorithm> ///sort, unique

using namespace std;

typedef pair<int, int> Pair;

list<vector<int> > answ;

void bicon(vector<vector<int> >& adjList, vector<Pair>& nds,
		int v, int pV, int ind, stack<Pair>& s) {
	nds[v].first = nds[v].second = ind;
	++ind;

	for(auto i=adjList[v].begin(); i!=adjList[v].end(); ++i) {
		if(*i == pV) continue;
		if(nds[*i].first == -1) {
			s.push(Pair(v, *i));
			bicon(adjList, nds, *i, v, ind, s);
			nds[v].second = min(nds[v].second, nds[*i].second);
			if(nds[*i].second >= nds[v].first) {
				auto comp = vector<int>();
				int c1, c2;
				do {
					c1 = s.top().first;
					c2 = s.top().second;
					s.pop();
					comp.push_back(c1);
					comp.push_back(c2);
				} while(c1 != v || c2 != *i);
				sort(comp.begin(), comp.end());
				comp.erase(unique(comp.begin(), comp.end()), comp.end());
				answ.push_back(comp);
			}
		} else nds[v].second = min(nds[v].second, nds[*i].first);
	}
}

int main() {
	ifstream inStr("biconex.in");
	ofstream outStr("biconex.out");

	int N, M;
	inStr >> N >> M;

	vector<vector<int> > adjList(N);
	
	int from, to;
	for(int i=0; i<M; ++i) {
		inStr >> from >> to;
		adjList[--from].push_back(--to);
		adjList[to].push_back(from);
	}

	stack<Pair> s;
	vector<Pair> nds(N, Pair(-1, 0));
	int ind = 0;
	bicon(adjList, nds, 0, -1, ind, s);

	outStr << answ.size() << '\n';

	for(auto comp:answ) {
		for(auto i=comp.begin(); i!=comp.end(); ++i)
			outStr << *i + 1 << ' ';
		outStr << '\n';
	}

	return 0;
}