Cod sursa(job #3178967)

Utilizator David8406Marian David David8406 Data 2 decembrie 2023 19:54:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <climits>
#include <set>
#include <string>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> v[100005], componente[100005];
stack <int> s;
int ind[100005], idx, low_link[100005], nrc;
bool in_stack[100005];
void Tarjan(int nod) {
	s.push(nod);
	in_stack[nod] = true;
	idx++;
	ind[nod] = idx;
	low_link[nod] = idx;
	for (auto el : v[nod]) {
		if (ind[el] == 0) {
			Tarjan(el);
			low_link[nod] = min(low_link[nod], low_link[el]);
		}
		else if (in_stack[el]) {
			low_link[nod] = min(low_link[nod], ind[el]);
		}
	}
	if (low_link[nod] == ind[nod]) {
		nrc++;
		while (!s.empty()) {
			in_stack[s.top()] = false;
			componente[nrc].push_back(s.top());
			if (s.top() == nod) {
				s.pop();
				break;
			}
			s.pop();
		}
	}
}
int main() {
	int n, m;
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		fin >> x >> y;
		v[x].push_back(y);
	}
	for (int i = 1; i <= n; i++)
		if (ind[i] == 0) Tarjan(i);
	fout << nrc << "\n";
	for (int i = 1; i <= n; i++) {
		for (auto el : componente[i]) fout << el << " ";
		fout << "\n";
	}
}