Pagini recente » Cod sursa (job #97219) | Cod sursa (job #1780782) | Cod sursa (job #1313078) | Cod sursa (job #2703813) | Cod sursa (job #3199100)
#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";
}
}