Pagini recente » Cod sursa (job #2100159) | Cod sursa (job #1123201) | Cod sursa (job #2824990) | Cod sursa (job #2000988) | Cod sursa (job #2120953)
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
std::ifstream in("ctc.in");
std::ofstream out("ctc.out");
const int MAX = 100000;
std::vector<int> Graf[MAX];
std::stack<int> Stack;
int index[MAX];
int lowlink[MAX];
std::bitset<MAX> instack;
int _index = 1;
int _results = 0;
std::vector< std::vector<int> > results;
void strongconnect(int v) {
index[v] = lowlink[v] = _index++;
Stack.push(v);
instack[v] = true;
for (int w : Graf[v]) {
if (index[w] == 0) {
strongconnect(w);
lowlink[v] = (lowlink[w] > lowlink[v]) ? lowlink[v] : lowlink[w];
}
else if (instack[w]) {
lowlink[v] = (index[w] > lowlink[v]) ? lowlink[v] : index[w];
}
}
if (lowlink[v] == index[v]) {
int w;
std::vector<int> result;
do {
w = Stack.top(); Stack.pop();
instack[w] = false;
result.push_back(w);
} while (w != v);
if (result.size() == 1 && result[0] == 0);
else {
_results++;
results.push_back(result);
}
}
}
int main() {
std::ios::sync_with_stdio(false);
int n, m;
in >> n >> m;
for (int i = 0; i < m; ++i) {
int x, y;
in >> x >> y;
Graf[x].push_back(y);
}
for (int i = 0; i < n; ++i) {
if (index[i] == 0) {
strongconnect(i);
}
}
out << _results << '\n';
for (std::vector<int> r : results) {
for (int val : r) {
out << val << ' ';
}
out << '\n';
}
return 0;
}