Cod sursa(job #2861219)

Utilizator alextmAlexandru Toma alextm Data 3 martie 2022 18:18:22
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 1e5 + 5;

int nrSCC, cnt;
int id[MAXN], low[MAXN], inStack[MAXN];
vector<int> G[MAXN], SCC[MAXN];
stack<int> st;

inline void dfs(int node) {
	id[node] = low[node] = ++cnt;
	st.push(node);
	inStack[node] = 1;
	
	for(auto vecin : G[node]) {
		if(id[vecin] == 0)
			dfs(vecin);
		if(inStack[vecin] == 1)
			low[node] = min(low[node], low[vecin]);
	}
	
	if(id[node] == low[node]) {
		nrSCC++;
		int x;
		do {
			x = st.top();
			SCC[nrSCC].push_back(x);
			low[x] = low[node];
			inStack[x] = 0;
			st.pop();
		} while( x != node );
	}
}

int main() {
	int n, m, x, y;
	fin >> n >> m;
	
	while(m--) {
		fin >> x >> y;
		G[x].push_back(y);
	}
	
	for(int i = 1; i <= n; i++)
		if(!id[i])
			dfs(i);
	
	fout << nrSCC << '\n';
	for(int i = 1; i <= nrSCC; i++) {
		for(int node : SCC[i])
			fout << node << ' ';
		fout << '\n';
	}
	
	return 0;
}