Cod sursa(job #3149809)

Utilizator daristyleBejan Darius-Ramon daristyle Data 12 septembrie 2023 19:05:40
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int NODES_MAX = 1e5;
vector<int> edge[NODES_MAX];
vector<int> revEdge[NODES_MAX];
vector<int> stronglyConnectedComponents[NODES_MAX];
vector<int> orderStack;
bool marked[NODES_MAX];

inline void addEdge(int u, int v){
	edge[u].push_back(v);
	revEdge[v].push_back(u);
}

template<typename T>
void reset(T v[], int n, T val){
	for(int i = 0; i < n; ++i)
		v[i] = val;
}

void dfs(const int& node, const vector<int>* edge, vector<int>& visited){
	marked[node] = true;

	for(auto neighbour: edge[node])
		if(!marked[neighbour])
			dfs(neighbour, edge, visited);

	visited.push_back(node);
}

int main(){
	int nodes, edges, u, v;
	fin >> nodes >> edges;
	for(int i = 0; i < edges; ++i){
		fin >> u >> v;

		addEdge(u - 1, v - 1);
	}

	for(int node = 0; node < nodes; ++node)
		if(!marked[node])
			dfs(node, edge, orderStack);

	reset(marked, nodes, false);

	int noSCC = 0;
	while(!orderStack.empty()){
		int node = orderStack.back();
		orderStack.pop_back();

		if(!marked[node]){
			dfs(node, revEdge, stronglyConnectedComponents[noSCC]);
			++noSCC;
		}
	}

	fout << noSCC << '\n';
	for(int i = 0; i < noSCC; ++i){
		for(auto x: stronglyConnectedComponents[i])
			fout << x + 1 << ' ';
		fout.put('\n');
	}

	fin.close();
	fout.close();
	return 0;
}