Cod sursa(job #2928874)

Utilizator NFJJuniorIancu Ivasciuc NFJJunior Data 24 octombrie 2022 01:03:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
#define cin f
#define cout g
const int Max = 1e5 + 1;

int n, m, visited[Max];
vector<int> adj[Max], adjR[Max];
vector<vector<int>> ans;
stack<int> post;

void DFS(int k)
{
	visited[k] = 1;
	for(auto it : adj[k])
		if(visited[it] == 0)
			DFS(it);

	post.push(k);
}

void DFSR(int k)
{
	visited[k] = 1;
	ans[ans.size() - 1].push_back(k);
	for(auto it : adjR[k])
		if(visited[it] == 0)
			DFSR(it);

}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i ++)
	{
		int x, y;
		cin >> x >> y;
		adj[x].push_back(y);
		adjR[y].push_back(x);
	}

	for(int i = 1; i <= n; i ++)
		if(visited[i] == 0)
			DFS(i);

	for(int i = 1; i <= n; i ++)
		visited[i] = 0;

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

		if(visited[top] == 0)
		{
			ans.push_back({});
			DFSR(top);
		}
	}
	cout<<ans.size()<<'\n';
	for(auto it : ans)
	{
		for(auto elem : it)
			cout<<elem<<' ';
		cout<<'\n';
	}
	return 0;
}