Cod sursa(job #2424376)

Utilizator mateigabriel99Matei Gabriel mateigabriel99 Data 22 mai 2019 22:17:02
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
using namespace std;

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

int N, M, nrSol;
map<int, vector<int>> G, T, result;
map<int, bool> visited;
stack<int> tmp;

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

void DFS1(int node)
{
	visited[node] = true;
	for (auto child : G[node])
		if (!visited[child])
			DFS1(child);
	tmp.push(node);
}

void DFS2(int node)
{
	result[nrSol].push_back(node);
	visited[node] = true;
	for (auto child : T[node])
		if (!visited[child])
			DFS2(child);
}

int main()
{
	Read();

	for (int i = 1; i <= N; i++)
		if (!visited[i])
			DFS1(i);

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

	while (!tmp.empty())
	{
		int top = tmp.top();
		if (!visited[top])
		{
			nrSol++;
			DFS2(top);
		}
		tmp.pop();
	}

	fout << nrSol << "\n";
	for (int i = 1; i <= nrSol; i++)
	{
		for (auto r : result[i])
			fout << r << " ";
		fout << "\n";
	}

	return 0;
}