Cod sursa(job #1414341)

Utilizator darrenRares Buhai darren Data 2 aprilie 2015 15:37:44
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstring>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
vector<int> V[100002];
int niv[100002], minniv[100002];
int ST[100002];
bool S[100002];
vector<vector<int> > comp;

void Dfs(int x)
{
	S[x] = true;
	minniv[x] = niv[x];
	ST[++ST[0]] = x;
	
	for (auto nod : V[x])
		if (!S[nod])
		{
			niv[nod] = niv[x] + 1;
			Dfs(nod);
			
			minniv[x] = min(minniv[x], minniv[nod]);
			
			if (minniv[nod] >= niv[x])
			{
				comp.push_back(vector<int>());
				while (true)
				{
					comp.back().push_back(ST[ST[0]]);
					--ST[0];
					if (ST[ST[0] + 1] == nod) break;
				}
				comp.back().push_back(x);
			}
		}
		else if (niv[nod] < niv[x])
			minniv[x] = min(minniv[x], niv[nod]);
}

int main()
{
	ifstream fin("biconex.in");
	ofstream fout("biconex.out");
	
	fin >> N >> M;
	for (int i = 1, nod1, nod2; i <= M; ++i)
	{
		fin >> nod1 >> nod2;
		V[nod1].push_back(nod2);
		V[nod2].push_back(nod1);
	}
	
	for (int i = 1; i <= N; ++i)
		if (!S[i])
			Dfs(i);
	
	fout << comp.size() << '\n';
	for (auto c : comp)
	{
		for (auto nod : c)
			fout << nod << ' ';
		fout << '\n';
	}
	
	fin.close();
	fout.close();
}