Pagini recente » Cod sursa (job #2139801) | Cod sursa (job #730280) | Cod sursa (job #729905) | Cod sursa (job #3126217) | Cod sursa (job #3271035)
#include <string.h>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
/// Metoda Kosaraju
const int NMAX = 100000 + 2;
int n, m;
vector<int> ad[NMAX];
vector<int> antid[NMAX];
bool viz[NMAX];
void reset_viz(){memset(viz, 0, sizeof viz);}
stack<int> s;
vector<vector<int>> comp;
void dfs_makestack(const int x) {
viz[x] = 1;
for(auto v : ad[x]) {
if(!viz[v]) {
dfs_makestack(v);
}
}
s.push(x);
}
void dfs_unwindstack(const int x) {
viz[x] = 1;
comp.back().push_back(x);
for(auto v : antid[x]) {
if(!viz[v]) {
dfs_unwindstack(v);
}
}
}
int main() {
ifstream in("ctc.in");
ofstream out("ctc.out");
in >> n >> m;
for(int i = 0; i < m; i++) {
int from, to;
in >> from >> to;
ad[from].push_back(to);
antid[to].push_back(from);
}
/// Step 1: Build Stack
for(int i = 1; i <= n; i++) {
if(!viz[i]) {
dfs_makestack(i);
}
}
reset_viz();
/// Step 2: Unwind Stack
while(!s.empty()) {
const int x = s.top();
s.pop();
if(viz[x])
continue;
comp.push_back({});
dfs_unwindstack(x);
}
out << comp.size() << '\n';
for(auto v : comp) {
for(auto i : v) {
out << i << ' ';
}
out << '\n';
}
}