Pagini recente » Cod sursa (job #87201) | Cod sursa (job #2439272) | Cod sursa (job #2228863) | Cod sursa (job #1517224) | Cod sursa (job #3233949)
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
class Solutuion {
private:
size_t N;
size_t M;
vector<vector<size_t>> adj;
vector<size_t> start;
vector<size_t> low_link;
stack<size_t> st;
vector<bool> done;
vector<set<size_t>> ctc = vector<set<size_t>>();
size_t time = 0;
void dfs(size_t node, size_t src_time) {
st.push(node);
start[node] = ++time;
low_link[node] = time;
for (auto neigh : adj[node]) {
if (done[neigh] && start[neigh] < src_time)
continue;
if (start[neigh] == 0) {
dfs(neigh, src_time);
}
low_link[node] = min(low_link[node], low_link[neigh]);
}
done[node] = true;
if (low_link[node] == start[node]) {
ctc.push_back(set<size_t>());
while (true) {
ctc.back().insert(st.top());
if (!(st.top() == node)) {
st.pop();
} else {
st.pop();
break;
}
}
}
}
public:
explicit Solutuion(ifstream &in) {
in >> N >> M;
adj.resize(N + 1);
start.resize(N + 1, 0);
low_link.resize(N + 1, 0);
done.resize(N + 1, false);
size_t node1, node2;
for (size_t i = 1; i <= M; i++) {
in >> node1 >> node2;
adj[node1].push_back(node2);
}
}
vector<set<size_t>> solve() {
for (size_t node = 1; node <= N; node++)
if (start[node] == 0)
dfs(node, time + 1);
return ctc;
}
};
int main() {
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<set<size_t>> solution = Solutuion(in).solve();
out << solution.size() << endl;
for (auto sol : solution) {
copy(sol.begin(), sol.end(), ostream_iterator<size_t>(out, " "));
out << endl;
}
in.close();
out.close();
return 0;
}