Cod sursa(job #3181153)

Utilizator maiaauUngureanu Maia maiaau Data 6 decembrie 2023 16:21:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

ifstream f("ctc.in");
ofstream g("ctc.out");

const int N = 1e5+3;

int n, k;
vector<vector<int>> G, GT, ctc;
bitset<N> u;
stack<int> stk;

void read(), dfsG(int), dfsGT(int);

int main()
{
	read();
	for (int i = 1; i <= n; i++)
		if (!u[i]) dfsG(i);
	u.reset();
	while (!stk.empty()){
		int nod = stk.top(); stk.pop();
		if(u[nod]) continue;
		ctc.pb({}); dfsGT(nod);
		k++;
	}
	g << k << '\n';
	for (int i = 0; i < k; i++){
		for (auto it: ctc[i]) g << it << ' ';
		g << '\n';
	}

	return 0;
}

void read() {
	int m; f >> n >> m;
	G.resize(n+3); GT.resize(n+3);
	while (m--){
		int a, b; f >> a >> b;
		G[a].pb(b); GT[b].pb(a);
	}
}
void dfsG(int nod){
	u[nod] = 1;
	for (auto v: G[nod])
		if (!u[v]) dfsG(v);
	stk.push(nod);
}
void dfsGT(int nod){
	u[nod] = 1; ctc[k].pb(nod);
	for (auto v: GT[nod])
		if (!u[v]) dfsGT(v);
}