Pagini recente » Cod sursa (job #2264456) | Statistici Serghiuta Alexia (AlexiaSerghiuta) | Cod sursa (job #1855699) | Cod sursa (job #2832050) | Cod sursa (job #2878772)
#include <bits/stdc++.h>
#define dbg(x) if(COND) { cout << #x << "=" << x << "\n"; }
#define dbgv(x) if(COND) { cout << #x << ":\n"; for (auto k: x) cout << k << " "; cout << "\n"; }
#define dbgvm(x) if(COND) { cout << #x << ":\n";int ind = 0; for (auto k: x){cout << ind++ << ":"; for (auto p : k) cout << p << " ";cout << "\n"; } cout << "\n"; }
#define brk(x) if (x) COND = true; else COND = false;
//#define int long long
#define sep if (COND) {cout << "\n--------------------\n";}
using namespace std;
bool COND = true;
#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else // LOCAL
ifstream in("ctc.in");
ofstream out("ctc.out");
#endif
typedef vector<vector<int>> vmat;
vmat scc(vmat g) {
int n = (int)g.size() - 1;
//dbg(n);
vector<int> nodes,viz(n + 1 , 0);
auto rev = [&](vmat &g) {
vmat revg(n + 1);
for (int i = 1; i <= n; i++) {
for (auto k : g[i]) {
revg[k].push_back(i);
}
}
g = revg;
};
// dbgvm(g);
vmat components;
function<void(int,bool)> dfs = [&](int node, bool flag) {
if (flag == true) {
components[(int)components.size() - 1].push_back(node);
}
viz[node] = 1;
for (auto k : g[node]) {
// dbg(k);
if (viz[k] == 0) {
viz[k] = 1;
dfs(k , flag);
}
}
if (flag == false) {
nodes.push_back(node);
}
};
for (int i = 1; i <= n; i++) {
if (viz[i] == 0)
dfs(i , false);
}
rev(g); /// reverses the graph
//
// dbgv(nodes);
viz = vector<int> (n + 1, 0);
for (int i = (int)nodes.size() - 1; i >= 0; i--) { /// nodes keeps the nodes in reverse order of tout
int l = nodes[i];
if (viz[l] == 0) {
components.push_back({});
dfs(l , true);
}
}
//dbgvm(components);
return components;
}
int32_t main() {
int n,m;
in >> n >> m;
vmat g(n + 1);
for (int i = 1; i <= m; i++) {
int u,v;
in >> u >> v;
g[u].push_back(v);
}
vmat components = scc(g);
out << components.size() << "\n";
for (auto k : components) {
for (auto p : k) {
out << p << " ";
}
out << "\n";
}
}