Cod sursa(job #3312989)

Utilizator lucap06Apostolache Luca lucap06 Data 1 octombrie 2025 16:49:04
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>

using namespace std;

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

vector<int>G[100001];
vector<int>GT[100001];
vector<int>c;
vector<int>noduricc[100001];
bitset<100001>viz;
int nc;
int n, m;

void citire()
{
	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);
	}
}

void dfs(int k)
{
	viz[k] = 1;
	for (auto it : G[k])
		if (!viz[it])
			dfs(it);
	c.push_back(k);
}

void dfsT(int k, int ct)
{
	viz[k] = 1;
	noduricc[ct].push_back(k);
	for (auto it : GT[k])
		if(!viz[it])
			dfsT(it, ct);
}


void kosaraju()
{
	citire();
	for (int i = 1; i <= n; i++)
		if (!viz[i])
			dfs(i);
	viz.reset();
	int ct = 0;
	for(int i=c.size() - 1;i>=0;i--)
		if (!viz[c[i]])
		{
			ct++;
			dfsT(c[i], ct);
		}
	out << ct << "\n";
	for (int i = 1; i <= ct; i++)
	{
		sort(noduricc[i].begin(), noduricc[i].end());
		for (auto it : noduricc[i])
			out << it << " ";
		out << "\n";
	}
}

int main()
{
	kosaraju();
	return 0;
}