Pagini recente » Infoarena Monthly 2012, Runda 12 | Cod sursa (job #3202302) | Regulament preONI 2007 | Istoria paginii flux-si-cuplaj | Cod sursa (job #3294613)
#include <bits/stdc++.h>
using namespace std;
int main() {
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
fin >> n >> m;
vector<vector<int>> adj(n + 1);
for (int i = 1, x, y; i <= m; ++i) {
fin >> x >> y;
adj[x].push_back(y);
}
vector<int> low_link(n + 1, INT_MAX), index(n + 1, -1);
vector<bool> in_stack(n + 1);
stack<int> st;
int t = 0;
vector<vector<int>> ctcs;
function<void(int)> dfs = [&](int nod) -> void {
low_link[nod] = index[nod] = ++t;
st.push(nod);
in_stack[nod] = true;
for (int vec : adj[nod]) {
if (index[vec] == -1) {
dfs(vec);
low_link[nod] = min(low_link[nod], low_link[vec]);
} else if (in_stack[vec]) {
low_link[nod] = min(low_link[nod], index[vec]);
}
}
if (low_link[nod] == index[nod]) {
int x;
vector<int> ctc;
do {
x = st.top(); st.pop();
ctc.push_back(x);
in_stack[x] = false;
} while (x != nod);
ctcs.push_back(ctc);
}
};
for (int i = 1; i <= n; ++i) {
if (index[i] == -1) {
dfs(i);
}
}
fout << ctcs.size() << '\n';
for (auto& ctc : ctcs) {
for (int val : ctc) {
fout << val << ' ';
}
fout << '\n';
}
return 0;
}