Cod sursa(job #3318649)

Utilizator r0scatRosca Teodora Maia r0scat Data 28 octombrie 2025 13:36:19
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.07 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
using namespace std;

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

// COMPONENTE TARE CONEXE
// ALGORITMUL LUI KOSARAJU

// 
// ord nodurile descrescator dupa timpul de iesire 
// dfs1(nod)
// vis1[nod] = 1
// for vecin in l[nod]
//		if vizitat[vecin] == 0
//			dfs1(vecin)
// v.pushback(nod);
// 
// 
// dfs2(nod)
// viz 2 va fi id-ul componentei in care se afla
// viz2[nod] = ctc
// for vecin in ltranspus[nod]
//		if(viz2[vecin] == 0
//			dfs2(vecin)
// 
// 
// 
// 
// for (i = 1; i <=n ...)
//		if (viz[i] == 0
//			dfs1(i)
// for(i = v.size() - 1; i >= 0; i--)
//		if(viz2[v[i] == 0)
//			ctc++;
//			dfs2(v[i])
// 
// print(ctc)
// print(vis2)
// 

int viz1[1000001], viz2[1000001], ctc; // ctc = nr comp tare conexe
vector<int> l[1000001], lt[1000001], v;

void dfs1(int nod) {
	viz1[nod] = 1;
	for (auto vecin : l[nod]) {
		if (viz1[vecin] == 0)
			dfs1(vecin);
	}
	v.push_back(nod);
}

void dfs2(int nod) {
	viz2[nod] = ctc;
	for (auto vecin : lt[nod]) {
		if (viz2[vecin] == 0)
			dfs2(vecin);
	}
}

int main() {
	int n, m;
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		fin >> x >> y;
		l[x].push_back(y);
		lt[y].push_back(x);
	}

	for (int i = 1; i <= n; i++) {
		if (viz1[i] == 0)
			dfs1(i);
	}
	ctc = 0;
	for (int i = v.size() - 1; i >= 0; i--)
		if (viz2[v[i]] == 0) {
			ctc++;
			dfs2(v[i]);
		}
					
	fout << ctc << "\n";
	fout << 1 << " ";
	for (int i = 2; i <= n; i++) {
		if (viz2[i] > viz2[i - 1])
			fout << "\n";
		fout << i << " ";
	}
		
}






// EXERCITIU BERARII
//
//ifstream fin("berarii2.in");
//
//// berarii
//vector<int> l[1000001];
//
//int main() {
//	int n, m, p;
//	fin >> n >> m >> p;
//	for (int i = 1; i <= m; i++)
//	{
//		int x, y;
//		fin >> x >> y;
//		l[x].push_back(y);
//	}
//
//
//}






// ------ALGORITM BFS
//
//ifstream fin("bfs.in");
//ofstream fout("bfs.out");
//
//// BFS
//// BFS(s)
//// s[1] = infinit;
//// s[start] = 0
//// q.push(start)
//// while !Q.empty()
////		nod = Q.front()
////
//
//int d[100001]; // distanta
//vector<int> l[100001]; // lista muchii
//queue<int> q;
//int n, m;
//
//
//void bfs(int start) {
//	for (int i = 1; i <= n; i++)
//		d[i] = -1;
//
//	d[start] = 0;
//	q.push(start);
//	while (!q.empty()) {
//		int nod = q.front();
//		q.pop();
//		for (auto vecin : l[nod]) {
//			if (d[vecin] == -1) {
//				d[vecin] = d[nod] + 1;
//				q.push(vecin);
//			}
//		}
//	}
//	for (int i = 1; i <= n; i++)
//		fout << d[i] << " ";
//}
//
//int main() {
//	int x, y, s;
//	fin >> n >> m >> s;
//	for (int i = 1; i <= m; i++)
//	{
//		fin >> x >> y;
//		l[x].push_back(y); // graf orientat
//	}
//	//cout << n << m << s;
//	bfs(s);
//}




/// ------PSEUDOCOD DFS
// parcurgerile in grafuri --> DFS si BFS
// componente tare conexe


// parcurgerea DFS
// 
// DFS(nod)
// vizitat[nod] = 1
// iteram prin toti vecinii nodului si ii marcam vizitat
// for vecin in L[nod] (lista de adiacenta)
//		if vizitat[vecin] == 0
//			DFS(vecin)
//
// pt a descoperii nr comp conexe
// for (i = 1; i <= n; i++)
//		if (vizitat[nod] == 0)
//			DFS(nod);
//			nrCompConexe++;
//

//-------------- ALGORITM DFS+ NR COMP CONEXE
//
//int vizitat[100001];
//vector<int> L[100001];
//
//
//void dfs(int nod) {
//	vizitat[nod] = 1;
//	for (int vecin : L[nod]) {
//		if (vizitat[vecin] == 0)
//			dfs(vecin);
//	}
//}
//
//int main()
//{
//	int n, m, x, y, nrCompConex = 0;
//	fin >> n >> m;
//	for (int i = 1; i <= m; i++) {
//		fin >> x >> y;
//		L[x].push_back(y);
//		L[y].push_back(x);
//	}
//
//
//	/*for (int i = 1; i <= n; i++)
//	{
//		cout << "nodul " << i << " are vecinii: ";
//		for (int j = 0; j < L[i].size(); j++)
//			cout << L[i][j] << " ";
//		cout << "\n";
//	}*/
//
//	for (int i = 1; i <= n; i++)
//		if (vizitat[i] == 0) {
//			dfs(i);
//			nrCompConex++;
//		}
//
//	fout << nrCompConex << '\n';
//	return 0;
//}
//