Pagini recente » Borderou de evaluare (job #1567706) | Cod sursa (job #1542100) | Cod sursa (job #2133362) | Cod sursa (job #1929685) | Cod sursa (job #2778012)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
std::ifstream fin ("ctc.in");
std::ofstream fout ("ctc.out");
int const nmax = 100000;
std::vector <std::vector <int>> adj;
std::vector <std::vector <int>> ans;
int cntans;
std::stack <int> st;
bool inStack[nmax + 5];
int lvl[nmax + 5];
int minlvl[nmax + 5];
int level = 1;
void solve (int x) {
lvl[x] = level++;
minlvl[x] = lvl[x];
inStack[x] = true;
st.push (x);
int lim = adj[x].size();
for (int i = 0; i < lim; i++) {
if (lvl[adj[x][i]] == 0) {
solve (adj[x][i]);
minlvl[x] = std::min (minlvl[x], minlvl[adj[x][i]]);
} else if (inStack[adj[x][i]])
minlvl[x] = std::min (minlvl[x], lvl[adj[x][i]]);
}
if (lvl[x] == minlvl[x]) {
ans.push_back({});
while (!st.empty() && st.top() != x) {
ans[cntans].push_back(st.top());
inStack[st.top()] = false;
st.pop();
}
if (!st.empty()) {
ans[cntans].push_back(st.top());
inStack[st.top()] = false;
st.pop();
}
cntans++;
}
}
int main()
{
int n, m;
fin >> n >> m;
adj.resize (n + 1);
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
adj[x].push_back(y);
}
for (int i = 1; i <= n; i++)
if (lvl[i] == 0)
solve (i);
fout << cntans << "\n";
for (int i = 0; i < cntans; i++) {
int lim = ans[i].size();
for (int j = 0; j < lim; j++)
fout << ans[i][j] << " ";
fout << "\n";
}
return 0;
}