Pagini recente » Cod sursa (job #1430508) | Cod sursa (job #1431947) | Cod sursa (job #127641) | Cod sursa (job #128351) | Cod sursa (job #1413482)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using Graph = std::vector<std::vector<int>>;
const int NMAX = 100005;
Graph G(NMAX);
std::vector<int> indexes(NMAX, -1);
std::vector<int> lowlinks(NMAX);
std::vector<bool> onstack(NMAX);
void tarjan(int node,
std::vector<std::vector<int>> &comps,
std::stack<int> &st,
int &curr_idx)
{
++curr_idx;
indexes[node] = lowlinks[node] = curr_idx;
st.emplace(node);
onstack[node] = true;
for (auto &neigh : G[node]) {
if (indexes[neigh] == -1) {
tarjan(neigh, comps, st, curr_idx);
lowlinks[node] = std::min(lowlinks[node], lowlinks[neigh]);
} else {
lowlinks[node] = std::min(lowlinks[node], lowlinks[neigh]);
}
}
if (indexes[node] == lowlinks[node]) {
std::vector<int> comp;
int curr = -1;
while (!st.empty() && curr != node) {
curr = st.top();
st.pop();
onstack[curr] = false;
comp.emplace_back(curr);
}
comps.emplace_back(comp);
}
}
int main()
{
std::ifstream fin{"ctc.in"};
std::ofstream fout{"ctc.out"};
int N, M;
fin >> N >> M;
for (auto i = 0; i < M; ++i) {
int x, y;
fin >> x >> y;
G[x - 1].push_back(y - 1);
}
std::vector<std::vector<int>> comps;
int start_idx = 0;
std::stack<int> st;
for (auto i = 0; i < N; ++i)
if (indexes[i] == -1)
tarjan(i, comps, st, start_idx);
fout << comps.size() << '\n';
for (auto &comp : comps) {
for (auto &elem : comp)
fout << elem + 1 << ' ';
fout << '\n';
}
return 0;
}