Cod sursa(job #1784803)

Utilizator ArkinyStoica Alex Arkiny Data 20 octombrie 2016 15:20:36
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

ifstream in("biconex.in");
ofstream out("biconex.out");

vector<int> G[100010],biconex[1000010],stk;

int N, M, viz[100010], time[100010], min_time[100010], tm,nr;

void tarjan(int x,int f)
{
	viz[x] = 1;
	stk.push_back(x);
	for (int i = 0;i < G[x].size();++i)
		if (!viz[G[x][i]])
		{
			time[G[x][i]] = min_time[G[x][i]] = ++tm;

			tarjan(G[x][i],x);

			if (time[x] <= min_time[G[x][i]])
			{
				++nr;

				while (stk.back() != G[x][i])
					biconex[nr].push_back(stk.back()), stk.pop_back();

				stk.pop_back();
				biconex[nr].push_back(G[x][i]);
				biconex[nr].push_back(x);
			}
			min_time[x] = min(min_time[x], min_time[G[x][i]]);
		}
		else if(G[x][i] != f)
			min_time[x] = min(min_time[x], min_time[G[x][i]]);
}

int main()
{
	in >> N >> M;

	for (int i = 1;i <= M;++i)
	{
		int x, y;
		in >> x >> y;

		G[x].push_back(y);
		G[y].push_back(x);
	}

	tarjan(1,0);

	out << nr << "\n";

	for (int i = 1;i <= nr;++i)
	{
		for (int j = 0;j < biconex[i].size();++j)
			out << biconex[i][j] << " ";
		out << "\n";
	}
	

	return 0;
}