Cod sursa(job #2471403)

Utilizator Carol_LucaCarol Luca Carol_Luca Data 10 octombrie 2019 20:35:41
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb

#include <vector>

#include <algorithm>

#include <queue>

#include <map>

#include <set>

#include <unordered_map>

#include <time.h>

#include <iomanip>

#include <deque>

#include <math.h>

#include <assert.h>

#include <stack>

#include <bitset>

#include <random>



using namespace std;



//-----------------------------------------------------------------



#include <fstream>



//ifstream cin("input"); ofstream cout("output");

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



const int inf = 1e9;

const int MAXN = 1e5 + 10;



vector < int > gr[MAXN];

vector < int > inv[MAXN];



int used[MAXN];



vector < int > ord;

vector < int > aux;

vector < vector < int > > ans;



void dfs(int nod) {

	used[nod] = 1;

	for (auto& x : gr[nod]) {

		if (!used[x]) {

			dfs(x);

		}

	}

	aux.push_back(nod);

}



int main() {



	int n, m;

	cin >> n >> m;



	while (m--) {

		int a, b;

		cin >> a >> b;

		gr[a].push_back(b);

		inv[b].push_back(a);

	}



	for (int i = 1; i <= n; i++) {

		if (!used[i]) {

			dfs(i);

			for (auto& x : aux) {

				ord.push_back(x);

			}

			aux.clear();

		}

	}



	reverse(ord.begin(), ord.end());



	for (int i = 1; i <= n; i++) {

		used[i] = 0;

		gr[i] = inv[i];

	}



	for (auto& x : ord) {

		if (!used[x]) {

			dfs(x);

			ans.push_back(aux);

			aux.clear();

		}

	}



	cout << ans.size() << '\n';

	for (auto& x : ans) {

		for (auto& y : x) {

			cout << y << " ";

		}

		cout << '\n';

	}





	return 0;

}