Pagini recente » Cod sursa (job #1687843) | Cod sursa (job #3291114) | Cod sursa (job #1021279) | Cod sursa (job #1640541) | Cod sursa (job #1963436)
/*
skel_graph - DFS
*/
#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#define NMAX 100001
using namespace std;
int n, m;
vector<int> G[NMAX];
vector<int> Gp[NMAX];
vector<int> dfs_vect;
bitset<NMAX> used;
vector<vector<int>> ctc;
vector<int> partial;
void read_input() {
int x, y;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &x, &y);
G[x].push_back(y);
Gp[y].push_back(x);
}
}
void dfsG(int node) {
used[node] = 1;
for (auto it = G[node].begin(); it != G[node].end(); ++it)
if (!used[*it]) dfsG(*it);
dfs_vect.push_back(node);
}
void dfsGp(int node) {
used[node] = 1;
for (auto it = Gp[node].begin(); it != Gp[node].end(); ++it)
if (!used[*it]) dfsGp(*it);
partial.push_back(node);
}
void solve() {
// Efectuam sortarea topologica
for (int i = 1; i <= n; ++i)
if (!used[i])
dfsG(i);
// Resetam bitsetul
used.reset();
// Cautam CTC-urile
for (int i = dfs_vect.size() - 1; i >= 0; --i) {
if (!used[dfs_vect[i]]) {
dfsGp(dfs_vect[i]);
ctc.push_back(partial);
partial.clear();
}
}
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
read_input();
solve();
printf("%d\n", ctc.size());
for (int i = 0; i < ctc.size(); ++i) {
for (int j = 0; j < ctc[i].size(); ++j) {
printf("%d ", ctc[i][j]);
}
printf("\n");
}
fclose(stdout);
fclose(stdin);
return 0;
}