Pagini recente » Cod sursa (job #202824) | Cod sursa (job #2743418) | Cod sursa (job #2352446) | Cod sursa (job #114492) | Cod sursa (job #2904928)
#include <bits/stdc++.h>
std::vector<std::vector<int>> res;
std::stack<int> st;
std::vector<bool> curr_st;
void dfs(std::vector<std::vector<int>>& g, std::vector<int>& found,
std::vector<int>& low_link, int& timestamp,
int curr) {
found[curr] = ++timestamp;
low_link[curr] = found[curr];
st.push(curr);
curr_st[curr] = true;
for (auto node : g[curr]) {
if (found[node] != -1) {
// visited
// -- check if it is in
// the current stack
if (curr_st[node]) {
low_link[curr] = std::min(low_link[curr], found[node]);
}
continue;
}
// not visited
dfs(g, found, low_link, timestamp, node);
low_link[curr] = std::min(low_link[curr], low_link[node]);
}
if (low_link[curr] == found[curr]) {
// no back edges from node
std::vector<int> scc;
do {
int node = st.top();
st.pop();
curr_st[node] = false;
scc.push_back(node);
} while (scc.back() != curr);
res.push_back(scc);
}
}
void scc_tarjan(std::vector<std::vector<int>>& g, int V) {
std::vector<int> found(V + 1, -1);
std::vector<int> low_link(V + 1);
curr_st = std::vector<bool>(V + 1);
int timestamp;
int node;
for (node = 1; node <= V; ++node) {
if (found[node] == -1) {
timestamp = 0;
dfs(g, found, low_link, timestamp, node);
}
}
}
int main() {
FILE *fin = fopen("ctc.in", "r");
std::ofstream fout("ctc.out");
int V, E;
fscanf(fin, "%d%d", &V, &E);
std::vector<std::vector<int>> g(V + 1);
int i, x, y;
for (i = 0; i < E; ++i) {
fscanf(fin, "%d%d", &x, &y);
g[x].push_back(y);
}
scc_tarjan(g, V);
int N = res.size();
fout << N << "\n";
for (i = 0; i < N; ++i) {
for (auto node : res[i]) {
fout << node << " ";
}
fout << "\n";
}
return 0;
}