Cod sursa(job #3124107)

Utilizator Codrut112Codrut Copas Codrut112 Data 26 aprilie 2023 22:23:34
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, x, y, viz[100005], ctc;
vector<int>v1[100005], v2[100005], CT[100005];
stack<int>s;
void read() {
	f >> n;
	f >> m;
	for (int i = 1; i <= m; i++)
		f >> x >> y, v1[x].push_back(y), v2[y].push_back(x);
}

void DFS(int nod) {
	viz[nod] = 1;
	for (int i = 0; i < v1[nod].size(); i++)
	{
		int vecin = v1[nod][i];
		
		if (viz[vecin] == 0)DFS(vecin);
	}
	
	s.push(nod);
}

void DFS_TR(int nod) {
	
	viz[nod] = 2;
	CT[ctc].push_back(nod);
	for (int i = 0; i < v2[nod].size(); i++)
		if (viz[v2[nod][i]] == 1)DFS_TR(v2[nod][i]);
}
void solve() {
	for (int i = 1; i <= n; i++)
		if (viz[i] == 0)
		{
			DFS(i); 
		}

	while (s.size()) {
		int nod = s.top();

		
		if (viz[nod] == 1) {
			ctc++;
			DFS_TR(nod);
			
		}
		s.pop();
	}
}

void print() {
	g << ctc << '\n';
	for (int i = 1; i <= ctc; i++,g<<"\n")
		for (int j = 0; j < CT[i].size(); j++)
			g << CT[i][j] << " ";
}

int main() {
	read();
	solve();
	print();

}