Cod sursa(job #3179121)

Utilizator alexlazuLazureanu Alexandru Ioan alexlazu Data 3 decembrie 2023 00:34:58
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <unordered_map>
#include <set>

using namespace std;

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

const int N = 5e5 + 1;

int n, m;

stack<int> S;

vector<int> v[N] , tr[N];
vector<vector<int>> abonamente;
int viz[N] , pozitiv[N] , negativ[N];
vector<int> retele;

#define cin in
#define cout out

void dfp(int nod)
{
	viz[nod] = 1;
	pozitiv[nod] = 1;
	for (auto& i : v[nod])
	{
		if (viz[i] == 0)
			dfp(i);
	}
}

void dfm(int nod)
{
	negativ[nod] = 1;
	retele.push_back(nod);
	for (auto& i : tr[nod])
	{
		if (pozitiv[i] == 1 && negativ[i] == 0)
		{
			dfm(i);
		}
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int l1, l2;
		cin >> l1 >> l2;
		v[l1].push_back(l2);
		tr[l2].push_back(l1);
	}
	int k = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int i = 1; i <= n; i++)
			viz[i] = 0;
		if (negativ[i] == 0)
		{
			dfp(i);
			dfm(i);
			abonamente.push_back(retele);
			retele.clear();
		}
	}
	cout << abonamente.size() << '\n';
	for (int i = 0; i < abonamente.size(); i++)
	{
		for (auto & j : abonamente[i])
		{
			cout << j << ' ';
		}
		cout << '\n';
	}
}