Cod sursa(job #2927090)

Utilizator niculaandreiNicula Andrei Bogdan niculaandrei Data 19 octombrie 2022 13:21:43
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <stack>

using namespace std;

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

const int N_MAX = 1e5 + 5;

int N, M;

int onStack[N_MAX], index[N_MAX], lowlink[N_MAX], idx;
stack <int> S;
vector <int> G[N_MAX];

vector <vector <int>> Ans;

void strongConnect(int currNode) {
	index[currNode] = idx;
	lowlink[currNode] = idx;
	idx++;
	S.push(currNode);
	onStack[currNode] = 1;
	for (int node : G[currNode]) {
		if (index[node] == 0) {
			strongConnect(node);
			lowlink[currNode] = min(lowlink[currNode], lowlink[node]);
		}
		else if (onStack[node]) {
			lowlink[currNode] = min(lowlink[currNode], index[node]);
		}
	}
	if (index[currNode] == lowlink[currNode]) {
		vector <int> scc;
		while (!S.empty()) {
			int node = S.top();
			S.pop();
			onStack[node] = 0;
			scc.push_back(node);
		}
		Ans.push_back(scc);
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	fin >> N >> M;
	for (int i = 1; i <= M; i++) {
		int u, v;
		fin >> u >> v;
		G[v].push_back(u);
	}

	idx = 1;
	for (int i = 1; i <= N; i++) {
		if (index[i] == 0) {
			strongConnect(i);
		}
	}

	fout << Ans.size() << "\n";
	for (int i = 0; i < Ans.size(); i++) {
		for (int j = 0; j < Ans[i].size(); j++) {
			fout << Ans[i][j] << " ";
		}
		fout << "\n";
	}
	return 0;
}