Pagini recente » Cod sursa (job #2527241) | Cod sursa (job #3287479) | Borderou de evaluare (job #2371569) | Cod sursa (job #1494196) | Cod sursa (job #1494152)
#include <stdio.h>
#include <stack>
#include <vector>
#define maxdim 100005
using namespace std;
int n, m;
int viz[maxdim];
vector<int> G[maxdim], Gt[maxdim];
stack<int> st;
vector<vector<int>> sol;
void dfs1(int nod) {
viz[nod] = 1;
for (int vecin : G[nod]) {
if (!viz[vecin]) {
dfs1(vecin);
}
}
st.push(nod);
}
void dfs2(int nod, vector<int> &crt) {
viz[nod] = 0;
crt.push_back(nod);
for (int vecin : Gt[nod]) {
if (viz[vecin]) {
dfs2(vecin, crt);
}
}
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i) {
int x, y; scanf("%d %d", &x, &y);
G[x].push_back(y);
Gt[y].push_back(x);
}
for (int i = 1; i <= n; ++i) {
if (!viz[i]) {
dfs1(i);
}
}
while (!st.empty()) {
int nod = st.top(); st.pop();
if (viz[nod]) {
vector<int> crt;
dfs2(nod, crt);
sol.push_back(crt);
}
}
printf("%d\n", (int) sol.size());
for (vector<int> &crt : sol) {
for (int nod : crt) {
printf("%d ", nod);
}
printf("\n");
}
return 0;
}