Pagini recente » Cod sursa (job #1267283) | Cod sursa (job #2912831) | Cod sursa (job #667156) | Cod sursa (job #914442) | Cod sursa (job #2536651)
// Testez ceva
#include <stack>
#include <vector>
#include <fstream>
#define DMAX 100010
using std::stack;
using std::vector;
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
int n, m;
vector<int> ad[DMAX];
int id;
stack<int> st;
int lvl[DMAX];
int low[DMAX];
bool onStack[DMAX];
int nrSol;
vector<int> sol[DMAX];
void dfs(int at, int father) {
st.push(at);
onStack[at] = true;
lvl[at] = low[at] = lvl[father] + 1;
for (int i = 0; i < (int) ad[at].size(); i++) {
int to = ad[at][i];
if (!lvl[to]) {
dfs(to, at);
if (low[to] < low[at])
low[at] = low[to];
}
else if (onStack[to] && low[to] < low[at])
low[at] = low[to];
}
if (lvl[at] == low[at]) {
while (true) {
int node = st.top();
st.pop();
onStack[node] = false;
low[node] = lvl[at];
sol[nrSol].push_back(node);
if (node == at)
break;
}
nrSol++;
}
}
int main() {
int a, b;
fin >> n >> m;
for (int i = 0; i < m; i++) {
fin >> a >> b;
ad[a].push_back(b);
}
int cnt = 0;
for (int i = 1; i <= n; i++)
if (!lvl[i]) {
if (++cnt == 2)
while (true);
dfs(i, 0);
}
fout << nrSol << '\n';
for (int i = 0; i < nrSol; i++) {
for (int j = 0; j < (int) sol[i].size(); j++)
fout << sol[i][j] << ' ';
fout << '\n';
}
fout.close();
return 0;
}