Cod sursa(job #1856183)

Utilizator ArkinyStoica Alex Arkiny Data 24 ianuarie 2017 17:02:11
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<fstream>
#include<vector>
#include<iostream>
#include<chrono>
#include<queue>
#include<algorithm>
using namespace std;

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

vector<int> G[100010],GT[100010],stk;
int viz[100010];
int nr = 1;
vector<int> rez[100010];
void sort_top(int x)
{
	viz[x] = 1;
	for (int i = 0; i < G[x].size(); ++i)
		if (!viz[G[x][i]])
			sort_top(G[x][i]);

	stk.push_back(x);
	
}

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

	for (int i = 0; i < GT[x].size(); ++i)
	{
		if (!viz[GT[x][i]])
			DFS(GT[x][i]);
	}
	rez[nr].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);
		GT[y].push_back(x);
	}

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

	for (int i = 1; i <= N; ++i)
		viz[i] = 0;

	for (int i = stk.size() - 1; i >= 0; --i)
	{
		if (!viz[stk[i]])
		{
			DFS(stk[i]);
			++nr;

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

	return 0;
}