Cod sursa(job #2927323)

Utilizator Rares_StefanoiuRares Stefanoiu Rares_Stefanoiu Data 20 octombrie 2022 00:16:04
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 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()) {
			if (s.top() == root) {
				sec.push_back(s.top());
				low[s.top()] = index[root];
				on_stack[s.top()] = 0;
				s.pop();

				break;
			}
			on_stack[s.top()] = false;
			sec.push_back(s.top());
			low[s.top()] = index[root];
			s.pop();
			
		}
		final.push_back(sec);
		scc++;
	}
}

int main() {
	f >> n >> m;
	lista.resize(n + 1);
	for (int i = 1; i <= m; i++) {
		cin >> 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)
	{
		if (!sec.empty())
		{
			for (auto nr : sec)
				g << nr << " ";
			g << "\n";
		}
	}
		
}