Pagini recente » Borderou de evaluare (job #515378) | Borderou de evaluare (job #3004596) | Borderou de evaluare (job #85112) | Rezultatele filtrării | Cod sursa (job #2492127)
#define DM 100001
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream fi ("ctc.in");
ofstream fo ("ctc.out");
int n, m, a, b, idx, cnt;
stack <int> s;
vector <int> ctc[DM];
class Node {
public:
bool stack;
int index = -1, low;
vector <int> edges;
void addNode(int x) {
edges.push_back(x);
}
} v[DM];
void connect_component(int x) {
v[x].index = v[x].low = ++idx;
v[x].stack = true;
s.push(x);
for (auto i:v[x].edges) {
if (v[i].index == -1) {
connect_component(i);
v[x].low = min(v[i].low, v[x].low);
}
else if (v[i].stack)
v[x].low = min(v[x].low, v[i].index);
}
if (v[x].index == v[x].low) {
do {
ctc[cnt].push_back(s.top());
v[s.top()].stack = false;
s.pop();
} while (s.top() != x);
ctc[cnt].push_back(s.top());
v[s.top()].stack = false;
s.pop();
++cnt;
}
}
int main() {
fi >> n >> m;
for (int i = 1; i <= m; ++i) {
fi >> a >> b;
v[a].addNode(b);
}
for (int i = 1; i <= n; ++i)
if (v[i].index == -1)
connect_component(i);
fo << cnt << '\n';
for (int i = 0; i < cnt; ++i)
for (auto j:ctc[i])
fo << j << " \n"[j==ctc[i].back()];
return 0;
}