Pagini recente » Rating Hasmasan Dragos (hasmasandragos) | Monitorul de evaluare | Cod sursa (job #2688147) | Rating ciornohac loredana (loredana100) | Cod sursa (job #1971171)
#include <fstream>
#include <vector>
#include <iostream>
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], lowlink2[kMaxN], depth[kMaxN], current, stack[kMaxN], stack2[kMaxN];
int n, m, a, b, t, t2, nr;
bool is_in_stack[kMaxN], viz[kMaxN];
void dfs(int x) {
lowlink[x] = depth[x];
is_in_stack[x] = true;
for (auto y : G[x]) {
if (!depth[y]) {
depth[y] = depth[x] + 1;
dfs(y);
lowlink[x] = min(lowlink[x], lowlink[y]);
}
else if (is_in_stack[y]) {
lowlink[x] = min(lowlink[x], depth[y]);
}
}
// cerr << x << " " << lowlink[x] << "\n";
is_in_stack[x] = false;
}
void tarjan(int x) {
viz[x] = true;
stack2[++t2] = x;
if (lowlink[x] <= t2) {
lowlink[x] = lowlink[stack2[lowlink[x]]];
}
stack[++t] = x;
is_in_stack[x] = 1;
for (auto y : G[x]) {
if (is_in_stack[y]) {
lowlink[x] = min(lowlink[x], lowlink[y]);
}
}
for (auto y : G[x]) {
if (!viz[y]) {
tarjan(y);
lowlink[x] = min(lowlink[x], lowlink[y]);
}
}
// cout << x << " " << lowlink[x] << "\n";
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;
}
--t2;
}
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;
dfs(i);
}
}
for (int i = 1; i <= n; ++i) {
if (!viz[i]) {
tarjan(i);
}
}
fout << nr << "\n";
for (int i = 1; i <= nr; ++i) {
for (auto el : CC[i]) {
fout << el << " ";
}
fout << "\n";
}
}