Cod sursa(job #940976)

Utilizator forgetHow Si Yu forget Data 17 aprilie 2013 17:17:10
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

vector<vector<int> > adjl;
vector<int> index, lowlink;
stack<int> s;
int num = 0;
vector<vector<int> > ans;

void dfs(int i, int p)
{
	s.push(i);
	index[i] = lowlink[i] = ++num;
	for (vector<int>::iterator it = adjl[i].begin(); it != adjl[i].end(); ++it) {
		int v = *it;
		if (index[v] == 0) {
			dfs(v, i);
			if (lowlink[i] > lowlink[v])
				lowlink[i] = lowlink[v];
			if (index[i] <= lowlink[v]) {
				ans.push_back(vector<int>());
				while (s.top() != v) {
					ans.back().push_back(s.top());
					s.pop();
				}
				s.pop();
				ans.back().push_back(v);
				ans.back().push_back(i);
			}
		}
		else if (v != p)
			if (lowlink[i] > lowlink[v])
				lowlink[i] = lowlink[v];
	}
}

int main()
{
	ifstream fin("biconex.in");
	ofstream fout("biconex.out");
	
	int n, m;
	fin >> n >> m;
	adjl.resize(n+1);
	index.resize(n+1);
	lowlink.resize(n+1);
	int u, v;
	for (; m > 0; --m) {
		fin >> u >> v;
		adjl[u].push_back(v);
		adjl[v].push_back(u);
	}
	for (int i = 1; i <= n; ++i)
		if (index[i] == 0)
			dfs(i,0);
	fout << ans.size() << '\n';
	for (int i = ans.size()-1; i >= 0; --i) {
		for (int j = ans[i].size()-1; j >= 0; --j)
			fout << ans[i][j] << ' ';
		fout << '\n';
	}
	return 0;
}