Cod sursa(job #1782697)

Utilizator ArkinyStoica Alex Arkiny Data 18 octombrie 2016 15:14:43
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

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

vector<int> G[100010];

vector<int> rez[100010];
vector<int> stk;
int v[100010][2],nr,viz[1000010], rez_nr=1;

void tarjan(int x, int f)
{
	viz[x] = 1;
	for (int i = 0;i < G[x].size();++i)
		if (!viz[G[x][i]])
		{
			v[G[x][i]][0] = ++nr;
			v[G[x][i]][1] = ++nr;
			tarjan(G[x][i], x);
			v[x][1] = min(v[G[x][i]][1], v[x][1]);

			if (v[x][0] <= v[G[x][i]][1])
			{
				while (stk.size() && stk.back() != x)
					rez[rez_nr].push_back(stk.back()), stk.pop_back();

				rez[rez_nr].push_back(x);
				++rez_nr;

				stk.push_back(x);
			}

		}
		else if (G[x][i] != f)
		{
			v[x][1] = min(v[G[x][i]][1], v[x][1]);
		}
}

int main()
{
	int N, M;

	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);
	}

	for (int i = 1;i <= N;++i)
		if (!viz[i])
			tarjan(i, 0);
	--rez_nr;
	out << rez_nr << '\n';
	for (int i = 1;i <= rez_nr;++i)
	{
		for (int j = 0;j < rez[i].size();++j)
			out << rez[i][j] << " ";
		out << '\n';
	}

	return 0;
}