Pagini recente » Cod sursa (job #2032538) | Cod sursa (job #2536843) | Cod sursa (job #2916444) | Cod sursa (job #801865) | Cod sursa (job #3227019)
#include <fstream>
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
const int mxN = 1e5 + 5;
std::vector<int> edges[mxN];
int timestamp, curr_size_ans;
std::vector<std::vector<int> > ans;
std::bitset<100005> visited;
std::bitset<100005> in_stack;
std::stack<int> visiting;
int found[mxN], low_link[mxN];
void dfs(int curr_node) {
found[curr_node] = ++timestamp;
low_link[curr_node] = found[curr_node];
visited[curr_node] = true;
visiting.push(curr_node);
in_stack[curr_node] = true;
for (auto neigh : edges[curr_node]) {
if (!visited[neigh]) {
dfs(neigh);
low_link[curr_node] = std::min(low_link[curr_node], low_link[neigh]);
} if (visited[neigh] && in_stack[neigh]) {
low_link[curr_node] = std::min(low_link[curr_node], low_link[neigh]);
}
}
if (found[curr_node] == low_link[curr_node]) {
std::vector<int> new_comp;
while (visiting.top() != curr_node) {
new_comp.push_back(visiting.top());
in_stack[visiting.top()] = false;
visiting.pop();
}
new_comp.push_back(visiting.top());
visiting.pop();
ans.push_back(new_comp);
}
}
int main() {
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
int n, m;
fin >> n >> m;
while (m--) {
int u, v;
fin >> u >> v;
edges[u].push_back(v);
}
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
dfs(i);
}
}
fout << ans.size() << '\n';
for (auto i = 0; i < ans.size(); ++i) {
std::vector<int> curr_comp = ans[i];
for (auto elem : curr_comp) {
fout << elem << " ";
}
fout << '\n';
}
return 0;
}