Cod sursa(job #2927113)

Utilizator niculaandreiNicula Andrei Bogdan niculaandrei Data 19 octombrie 2022 15:43:25
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 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;
		int node;
		do {
			node = S.top();
			S.pop();
			onStack[node] = 0;
			scc.push_back(node);
		} while (currNode != node);
		Ans.push_back(scc);
	}
}


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

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

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

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