Pagini recente » Cod sursa (job #941223) | Cod sursa (job #2135157) | Cod sursa (job #2280000) | Cod sursa (job #107135) | Cod sursa (job #3230209)
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>
#define NMAX 100000
struct Edge {
int x;
int y;
Edge() { }
Edge(int x, int y)
: x(x)
, y(y) { }
bool operator==(const Edge& other) { return x == other.x && y == other.y; }
bool operator!=(const Edge& other) { return !(*this == other); }
};
void tarjan(int node, std::vector<int> adj[], std::vector<Edge> &st,
int ×tamp, int found[], int low_link[],
std::vector<std::set<int>> &bccs)
{
++timestamp;
found[node] = timestamp;
low_link[node] = timestamp;
for (auto neigh : adj[node]) {
if (found[neigh] == -1) {
st.push_back({node, neigh});
tarjan(neigh, adj, st, timestamp, found, low_link, bccs);
low_link[node] = std::min(low_link[node], low_link[neigh]);
if (low_link[neigh] >= found[node]) {
Edge st_edge, first_edge(node, neigh);
bccs.push_back({});
do {
st_edge = st.back();
st.pop_back();
bccs.back().insert(st_edge.x);
bccs.back().insert(st_edge.y);
} while (st_edge != first_edge);
}
} else {
low_link[node] = std::min(low_link[node], found[neigh]);
}
}
}
int main()
{
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
int n, m;
std::vector<int> adj[NMAX];
int timestamp = 0, found[NMAX], low_link[NMAX];
std::vector<Edge> st;
std::vector<std::set<int>> bccs;
fin >> n >> m;
for (int v, w, i = 0; i < m; ++i) {
fin >> v >> w;
adj[v - 1].push_back(w - 1);
}
for (int i = 0; i < n; ++i)
found[i] = -1;
for (int i = 0; i < n; ++i)
if (found[i] == -1)
tarjan(i, adj, st, timestamp, found, low_link, bccs);
fout << bccs.size() << '\n';
for (auto bcc : bccs) {
for (auto node : bcc)
fout << node + 1 << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}