Pagini recente » Borderou de evaluare (job #830265) | Utilizatori inregistrati la ONIS 2014, Runda 3 | Utilizatori inregistrati la Infoarena Monthly 2012 - Runda 10 | Borderou de evaluare (job #1544314) | Cod sursa (job #1967605)
#include <fstream>
#include <vector>
using namespace std;
const int kMaxN = 1e5+10;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector<int> G[kMaxN], CC[kMaxN];
int lowlink[kMaxN], depth[kMaxN], current, stack[kMaxN], n, m, a, b, t, nr;
bool is_in_stack[kMaxN];
void tarjan(int x) {
lowlink[x] = depth[x];
is_in_stack[x] = 1;
stack[++t] = x;
for (auto y : G[x]) {
if (is_in_stack[y]) {
lowlink[x] = min(lowlink[x], lowlink[y]);
}
}
for (auto y : G[x]) {
if (!depth[y]) {
depth[y] = depth[x] + 1;
tarjan(y);
lowlink[x] = min(lowlink[x], lowlink[y]);
}
}
if (lowlink[x] == depth[x]) {
++nr;
while (stack[t] != x) {
CC[nr].push_back(stack[t]);
is_in_stack[stack[t]] = 0;
--t;
}
CC[nr].push_back(x);
is_in_stack[x] = 0;
--t;
}
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; ++i) {
fin >> a >> b;
G[a].push_back (b);
}
for (int i = 1; i <= n; ++i) {
if (!depth[i]) {
depth[i] = 1;
tarjan(i);
}
}
fout << nr << "\n";
for (int i = 1; i <= nr; ++i) {
for (auto el : CC[i]) {
fout << el << " ";
}
fout << "\n";
}
}