Pagini recente » Cod sursa (job #1986191) | Cod sursa (job #2543157) | Cod sursa (job #2831105) | Cod sursa (job #199404) | Cod sursa (job #1757202)
#include <algorithm>
#include <fstream>
#include <functional>
#include <stack>
#include <vector>
using namespace std;
vector<vector<int>> tarjan(const vector<vector<int>>& graph) {
vector<vector<int>> ans;
vector<bool> in_stack(graph.size());
vector<int> idx(graph.size(), -1);
vector<int> lowlink(graph.size());
stack<int> st;
int index = 0;
function<void(int)> dfs;
dfs = [&](int node) -> void {
idx[node] = lowlink[node] = index++;
st.push(node);
in_stack[node] = true;
for (int n : graph[node]) {
if (idx[n] == -1) {
dfs(n);
lowlink[node] = min(lowlink[node], lowlink[n]);
} else if (in_stack[n]) {
lowlink[node] = min(lowlink[node], lowlink[n]);
}
}
if (idx[node] == lowlink[node]) {
vector<int> con;
int n;
do {
con.push_back(n = st.top());
st.pop();
in_stack[n] = false;
} while (n != node);
ans.push_back(con);
}
};
for (int i = 1; i < (int) graph.size(); ++ i) if (idx[i] == -1)
dfs(i);
return ans;
}
int main() {
vector<vector<int>> graph;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
fin >> n >> m;
graph.resize(n + 1);
for (int iter = 0; iter < m; ++iter) {
int x, y;
fin >> x >> y;
graph[x].push_back(y);
}
auto ans = tarjan(graph);
fout << ans.size() << "\n";
for (auto comp : ans) {
for (int elem : comp) {
fout << elem << " ";
}
fout << "\n";
}
return 0;
}