Pagini recente » Cod sursa (job #1193054) | Cod sursa (job #2736369) | Cod sursa (job #504161) | Cod sursa (job #422332) | Cod sursa (job #1476420)
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int NMAX = 100505;
int n, m, st[NMAX], r;
vector<int> G[NMAX], GT[NMAX];
vector<vector<int>> sol;
bool mark[NMAX];
void read() {
scanf("%d%d", &n, &m);
int x, y;
for (int i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
G[x].push_back(y); GT[y].push_back(x);
}
}
void dfs1(int node) {
mark[node] = true;
for (auto y: G[node]) {
if (!mark[y]) {
dfs1(y);
}
}
st[++r] = node;
}
void dfs2(int node, vector<int>& sol) {
mark[node] = true;
sol.push_back(node);
for (auto y: GT[node]) {
if (!mark[y]) {
dfs2(y, sol);
}
}
}
void solve() {
// topological sort of the final DAG
for (int i = 1; i <= n; i++)
if (!mark[i])
dfs1(i);
// at each step we take the node with the highest POST ;
// a source node (no incoming edges) in the final DAG
// => a sink node in the final DAG transposed =>
// if we do a dfs on it, it will visit all the nodes in its
// connected component, but it won't visit any others
memset(mark, false, sizeof(mark));
for (int i = r; i >= 1; i--) {
if (!mark[st[i]]) {
sol.push_back(vector<int>());
dfs2(st[i], sol.back());
}
}
printf("%d\n", (int)sol.size());
for (auto entry: sol) {
for (size_t i = 0; i < entry.size(); i++) {
if (i > 0) printf(" ");
printf("%d", entry[i]);
}
printf("\n");
}
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
read();
solve();
return 0;
}