Cod sursa(job #1856517)

Utilizator ArkinyStoica Alex Arkiny Data 24 ianuarie 2017 23:47:06
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<fstream>
#include<vector>
#include<iostream>
#include<chrono>
#include<queue>
#include<algorithm>
#include<string.h>
using namespace std;

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

int viz[200010],a[200010],b[200010],nr=0,sz=0;
int in_stk[200010];
vector<int> G[200010];
vector<int> stk;
vector<int> rez[200010];
void Tarjan(int x)
{
	viz[x] = 1;
	stk.push_back(x);
	in_stk[x] = 1;
	for (int i = 0; i < G[x].size(); ++i)
	{
		if (!viz[G[x][i]])
		{
			++nr;
			a[G[x][i]] = nr;
			b[G[x][i]] = nr;

			Tarjan(G[x][i]);
			b[x] = min(b[x], b[G[x][i]]);
		}
		else if(in_stk[G[x][i]])
		{
			b[x] = min(b[x], b[G[x][i]]);
		}
	}

	if (b[x] == a[x])
	{
		++sz;
		while (stk.back() != x)
			rez[sz].push_back(stk.back()), stk.pop_back();

		stk.pop_back();
		rez[sz].push_back(x);
	}
}

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

	for (int i = 1; i <= N; ++i)
	{
		if (!viz[i])
			Tarjan(i);
	}

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

	return 0;
}