Cod sursa(job #2906264)

Utilizator Alin_StanciuStanciu Alin Alin_Stanciu Data 25 mai 2022 13:01:31
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#define MAX_N 100000

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

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

int N, M;
vector<int> G[MAX_N + 1];

vector<int> Nin[MAX_N + 1];
bool visited[MAX_N + 1];
stack<int> processed;
queue<int> q;
int c, comp[MAX_N + 1];
vector<vector<int>> C(1);

void DF1(int x)
{
	for (int y : G[x])
	{
		if (!visited[y])
		{
			visited[y] = true;
			DF1(y);
		}
	}

	processed.push(x);
}

void Algorithm()
{
	for (int i = 1; i <= N; ++i)
	{
		if (!visited[i])
			DF1(i);
	}

	for (int i = 1; i <= N; ++i)
		visited[i] = false;

	while (!processed.empty())
	{
		int r = processed.top();
		processed.pop();

		if (visited[r])
			continue;

		visited[r] = true;
		++c;
		q.push(r);
		C.emplace_back();

		while (!q.empty())
		{
			int y = q.front();
			q.pop();
			comp[y] = c;
			C.back().push_back(y);

			for (int x : Nin[y])
			{
				if (!visited[x])
				{
					visited[x] = true;
					q.push(x);
				}
			}
		}
	}
}

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

	for (int i = 0; i < M; ++i)
	{
		int x, y;
		fin >> x >> y;
		G[x].push_back(y);
		Nin[y].push_back(x);
	}

	Algorithm();

	fout << c << '\n';

	for (int i = 1; i <= c; ++i)
	{
		for (int x : C[i])
			fout << x << ' ';

		fout << '\n';
	}

	return 0;
}