Cod sursa(job #3199100)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 31 ianuarie 2024 19:21:00
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
ifstream in("ctc.in");
ofstream out("ctc.out");
#define cin in
#define cout out
#endif

const int nmax = 2e5 + 7;
vector<int> g[nmax]; // graful nostru
vector<int> reverse_g[nmax]; // graful nostru inversat
int viz[nmax]; // vizitat
int color[nmax]; // componenta tare conexa
vector<int> aproximare; // o aproximare a unei sortari topologice

// 	Primul DFS ne da o "aproximare" a unei sortari topologice (desi nu chiar)

void first_dfs(int node) {
	if(viz[node] == 1) return;
	viz[node] = 1;

	for(auto it : g[node]) {
		first_dfs(it);
	}

	aproximare.push_back(node);
}

// 	Al doilea DFS ne da o colorare a componentelor tare conexe

void second_dfs(int node, int culoare) {
	if(viz[node] == 2) return;
	viz[node] = 2; 
	color[node] = culoare;

	for(auto it : reverse_g[node]) {
		second_dfs(it, culoare);
	}
}

int main() {
	int n, m; cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		int x, y; cin >> x >> y;
		g[x].push_back(y);
		reverse_g[y].push_back(x);
	}

	for(int i = 1; i <= n; i++) {
		first_dfs(i);
	}
	reverse(aproximare.begin(), aproximare.end()); // inversam aproximarea
	// astfel incat sa putem sa o parcurgem de la sfarsit la inceput
	// apeland al doilea DFS

	int cnt_culoare = 0;

	for(auto node : aproximare) {
		if(viz[node] == 2) continue;
		cnt_culoare++;
		second_dfs(node, cnt_culoare);
	}

	vector<vector<int>> ctc(cnt_culoare + 1); // componentele tare conexe
	for(int i = 1; i <= n; i++) {
		ctc[color[i]].push_back(i);
	}

	cout << cnt_culoare << "\n";
	for(int i = 1; i <= cnt_culoare; i++) {
		for(auto it : ctc[i]) {
			cout << it << " ";
		}
		cout << "\n";
	}
}