Cod sursa(job #2927305)

Utilizator Rares_StefanoiuRares Stefanoiu Rares_Stefanoiu Data 19 octombrie 2022 23:29:12
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include<iostream>
#include<fstream>
#include<unordered_map>
#include<vector>
#include<stack>
using namespace std;
int n, m, n1, n2, i;
int id = 0, scc = 0;
vector<vector<int>>lista;
unordered_map<int, int>index;
unordered_map<int, int>low;
unordered_map<int, bool>on_stack;
vector<vector<int>> final;
stack<int>s;
ifstream f("ctc.in");
ofstream g("ctc.out");

void DFS(int root) {
	low[root] = ++id;
	index[root] = low[root];
	s.push(root);
	on_stack[root] = 1;
	for (auto el : lista[root])
	{
		if (index[el] == 0)
			DFS(el);
		if (on_stack[el])
			low[root] = min(low[root], low[el]);
	}
	if (low[root] == index[root])
	{
		vector<int>sec;
		while (!s.empty()) {
			on_stack[s.top()] = false;
			sec.push_back(s.top());
			s.pop();
			if (s.top() == root) {
				sec.push_back(s.top());
				break;
			}
		}
		final.push_back(sec);
		scc++;
	}
}

int main() {
	f >> n >> m;
	lista.resize(n + 1);
	for (int i = 1; i <= m; i++) {
		f >> n1 >> n2;
		lista[n1].push_back(n2);
	}

	for (i = 1; i <= n; i++)
		if (index[i] == 0)
			DFS(i);
	g << scc << "\n";
	for (auto sec : final)
	{
		for (auto nr : sec)
			g << nr << " ";
		g << "\n";
	}
		
}