Pagini recente » Profil M@2Te4i | Cod sursa (job #1282155) | Cod sursa (job #1365629) | Statistici Ovidiu Croitor (Ovidetzu) | Cod sursa (job #2017334)
#include <bits/stdc++.h>
const int MAX_N = 100000;
std::vector<int>G[1 + MAX_N];
std::vector<std::vector<int> >ctc;
std::stack<int>st;
int low[1 + MAX_N], lvl[1 + MAX_N];
bool viz[1 + MAX_N], inStiva[1 + MAX_N];
int order;
void dfs(int nod) {
viz[nod] = true;
low[nod] = lvl[nod] = ++order;
inStiva[nod] = true;
st.push(nod);
for (auto it:G[nod]) {
if (!viz[it])
dfs(it);
if (inStiva[it])
low[nod] = std::min(low[nod], low[it]);
}
if (low[nod] == lvl[nod]) {
std::vector<int>aux;
int tmp;
do {
tmp = st.top();
st.pop();
inStiva[tmp] = false;
aux.push_back(tmp);
} while (tmp != nod);
ctc.push_back(aux);
}
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
}
for (int i = 1; i <= n; ++i)
if (!viz[i])
dfs(i);
printf("%d\n", ctc.size());
for (auto it1:ctc) {
for (auto it2:it1)
printf("%d ", it2);
printf("\n");
}
return 0;
}