Cod sursa(job #2501951)

Utilizator VladAdrianaVlad Adriana VladAdriana Data 30 noiembrie 2019 12:08:28
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <vector>
#define pb push_back

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, x, y, nr, l, pst[100005],uz[100005];
vector <int> L[100005], Lt[100005], S[100005];
void dfs(int k)
{
	uz[k] = 1;
	for (int i = 0; i < L[k].size(); i++)
		if (!uz[L[k][i]])
			dfs(L[k][i]);
	pst[++l] = k;
}
void dfst(int k)
{
	uz[k] = 0;
	for (int i = 0; i < Lt[k].size(); i++)
		if (uz[Lt[k][i]])
			dfst(Lt[k][i]);
	S[nr].pb(k);
}
int main()
{
	int i,j;
	fin >> n >> m;
	for(i=1;i<=m;i++)
	{
		fin >> x >> y;
		L[x].pb(y);
		Lt[y].pb(x);
	}
	for (i = 1; i <= n; i++)
		if (!uz[i]) 
			dfs(i);
	for (i = n; i >= 1; i--)
		if (uz[pst[i]])
		{
			nr++;
			dfst(pst[i]);
		}
	fout << nr << '\n';
	for (i = 1; i <= nr; i++)
	{
		for (j = 0; j < S[i].size(); j++)
			fout << S[i][j] << ' ';
		fout << '\n';
	}
	return 0;
}