Pagini recente » Cod sursa (job #85325) | Cod sursa (job #2881689) | Cod sursa (job #335975) | Cod sursa (job #1690317) | Cod sursa (job #1166648)
#include <algorithm>
#include <bitset>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define len(x) int((x).size())
const int INF = 1 << 30;
const int MAX_N = 100100;
typedef vector<int> Graph[MAX_N];
int N, M;
Graph g, tg;
bitset<MAX_N> vis;
vector<vector<int>> ctc;
void kosaraju();
void dfs(int node, Graph g, vector<int> &st);
int main() {
fin >> N >> M;
for (int i = 1, a, b; i <= M; i += 1) {
fin >> a >> b;
g[a].push_back(b);
tg[b].push_back(a);
}
kosaraju();
fout << len(ctc) << '\n';
for (auto i: ctc) {
for (auto j: i) {
fout << j << ' ';
}
fout << '\n';
}
}
void kosaraju() {
vector<int> tp;
vis = 0;
for (int i = 1; i <= N; i += 1)
if (!vis[i]) dfs(i, g, tp);
vis = 0;
while (!tp.empty()) {
int node = tp.back();
tp.pop_back();
if (vis[node]) continue;
ctc.push_back(vector<int>());
dfs(node, tg, ctc.back());
}
}
void dfs(int node, Graph g, vector<int> &st) {
vis[node] = 1;
for (auto x: g[node])
if (!vis[x]) dfs(x, g, st);
st.push_back(node);
}