Pagini recente » Cod sursa (job #2560571) | Cod sursa (job #2111946) | Cod sursa (job #3254144) | Cod sursa (job #1277822) | Cod sursa (job #3353870)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NODES = 1e5 + 1;
int n, m, k;
//int adj[NODES][NODES];
// int rev[NODES][NODES];
vector<int> adj[NODES], rev[NODES];
vector<bool> viz(NODES,false);
stack<int> ord_st;
vector<vector<int>> components;
void init_dfs(int c) {
viz[c] = true;
for (const int &nxt : adj[c]) {
if (!viz[nxt]) {
init_dfs(nxt);
}
}
ord_st.push(c);
}
void rev_dfs(int c, vector<int> &comp) {
// printf(" rev_dfs(%d)\n", c);
viz[c] = true;
comp.push_back(c);
for (const int &nxt : rev[c]) {
// printf(" vreau sa merg in %d; viz: %d\n", nxt, (int)viz[nxt]);
if (!viz[nxt]) {
rev_dfs(nxt, comp);
}
}
}
void kosaraju() {
int i;
for (i = 1; i <= n; ++i) {
if (!viz[i]) {
init_dfs(i);
}
}
// // printf("gata dfs 1\n");
fill(viz.begin(), viz.end(), false);
while (!ord_st.empty()) {
// printf("ord_st are %lu elem\n", ord_st.size());
int top = ord_st.top();
// printf(" viz[%d] = %d\n", top, (int)viz[top]);
ord_st.pop();
if (!viz[top]) {
vector<int> comp;
// printf("dau rev_dfs(%d, comp, %lu)\n", top, components.size());
rev_dfs(top, comp);
components.push_back(comp);
}
}
}
int main() {
fin >> n >> m;
// printf("n %d m %d\n", n, m);
int i, x, y;
for (i = 0; i < m; ++i) {
fin >> x >> y;
// printf("%d -> %d\n", x, y);
adj[x].push_back(y);
rev[y].push_back(x);
}
kosaraju();
fout << components.size() << '\n';
for (auto comp : components) {
for (int v : comp) {
fout << v << ' ';
}
fout << '\n';
}
}