Cod sursa(job #2564599)

Utilizator ArkinyStoica Alex Arkiny Data 2 martie 2020 00:22:39
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

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

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

int N, M, viz[100010], n_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]])
		{
			n_time[G[x][i]] = min_time[G[x][i]] = ++tm;

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

			if (n_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;
}