Cod sursa(job #2719685)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 10 martie 2021 09:53:27
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

const int NMAX = 100005;

int n, m;

vector<bool>viz(NMAX);
vector<int>G[NMAX];
vector<int>Gt[NMAX];
vector<vector<int> >sol;
vector<int>c;
stack<int>st;

void dfs(int u)
{
	viz[u] = true;
	for (int v : G[u])
		if (!viz[v])
			dfs(v);
	st.push(u);
}

void dfsT(int u)
{
	viz[u] = true;
	for (int v : Gt[u])
		if (!viz[v])
			dfsT(v);
	c.push_back(u);
}

void read()
{
	fin >> n >> m;
	while (m--)
	{
		int a, b;
		fin >> a >> b;
		G[a].push_back(b);
		Gt[b].push_back(a);
	}
}

void solve()
{
	viz.assign(n + 5, 0);
	for (int i = 1; i <= n; i++)
		if (!viz[i])
			dfs(i);
	viz.assign(n + 5, 0);
	while (!st.empty())
	{
		int u = st.top();
		st.pop();
		c.clear();
		if (viz[u]) continue;
		dfsT(u);
		sol.push_back(c);
	}
	fout << sol.size() << '\n';
	for (int i = 0; i < sol.size(); i++)
	{
		sort(sol[i].begin(), sol[i].end());
		for (int e : sol[i])
			fout << e << ' ';
		fout << '\n';
	}
}

int main()
{
	read();
	solve();
	return 0;
}