Cod sursa(job #2193627)

Utilizator ArkinyStoica Alex Arkiny Data 10 aprilie 2018 19:27:33
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<fstream>
using namespace std;

int N, M;

vector<int> G[150010];
vector<int> G_DAG[150010];
int grade_in[150010];
int viz[150010];
int h[150010][2];
int id[150010];
int p;
int comp_conex_sz;
vector<int> stk;
vector<int> comp_conex[150010];
vector<int> rez;

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

void tarjan(int x)
{

	viz[x] = 1;

	h[x][0] = h[x][1] = p;

	++p;

	stk.push_back(x);

	for (int i = 0; i < G[x].size(); ++i)
	{
		if (!viz[G[x][i]])
		{
			tarjan(G[x][i]);
			h[x][1] = min(h[x][1], h[G[x][i]][1]);
		}
		else if(viz[G[x][i]] == 1)
		{
			h[x][1] = min(h[x][1], h[G[x][i]][1]);
		}
	}

	if (h[x][0] == h[x][1])
	{

		++comp_conex_sz;

		while (stk.back()!=x)
			comp_conex[comp_conex_sz].push_back(stk.back()), viz[stk.back()] = 2, id[stk.back()] = comp_conex_sz, stk.pop_back();

		stk.pop_back();
		comp_conex[comp_conex_sz].push_back(x);
		viz[x] = 2;
		id[x] = comp_conex_sz;
	}

	
}

void create_grades_dag(int x)
{
	viz[x] = 1;


	for (int i = 0; i < G[x].size(); ++i)
	{

		if (id[G[x][i]] != id[x])
		{
			grade_in[id[G[x][i]]]++;
			G_DAG[id[x]].push_back(id[G[x][i]]);
		}

		if (!viz[G[x][i]])
		{
			create_grades_dag(G[x][i]);
		}
	}
}

void sort_top(int x)
{
	viz[x] = 1;

	for (int i = 0; i < G_DAG[x].size(); ++i)
	{
		if (!viz[G_DAG[x][i]])
		{
			sort_top(G_DAG[x][i]);
		}
			
	}

	stk.push_back(x);

}

int main()
{
	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 << comp_conex_sz << "\n";

	for (int i = 1; i <= comp_conex_sz; ++i)
	{
		for (int j = 0; j < comp_conex[i].size(); ++j)
		{
			out << comp_conex[i][j] << " ";
		}

		out << "\n";
	}



	

	return 0;
}