Cod sursa(job #2816385)

Utilizator alextmAlexandru Toma alextm Data 11 decembrie 2021 12:31:11
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 101;

vector<int> G[MAXN], GT[MAXN], ans[MAXN];
bool viz[MAXN];
stack<int> st;

void dfs(int node) {
	viz[node] = 1;
	for(auto nxt : G[node])
		if(!viz[nxt])
			dfs(nxt);
	st.push(node);
}

void dfsGT(int node, int cnt) {
	viz[node] = 1;
	for(auto nxt : GT[node])
		if(!viz[nxt])
			dfsGT(nxt, cnt);
	ans[cnt].push_back(node);
}

int main() {
	int n, m, x, y;
	
	fin >> n >> m;
	while(m--) {
		fin >> x >> y;
		G[x].push_back(y);
		GT[y].push_back(x);
	}
	
	for(int i = 1; i <= n; i++)
		if(viz[i] == 0)
			dfs(i);
			
	memset(viz, 0, sizeof(viz));
	
	int ctc = 0;
	while(!st.empty()) {
		if(!viz[st.top()]) {
			ctc++;
			dfsGT(st.top(), ctc);
		}
		st.pop();
	}
	
	fout << ctc << "\n";
	for(int i = 1; i <= n; i++) {
		for(auto node : ans[i])
			fout << node << " ";
		fout << "\n";
	}
	
	return 0;
}