Pagini recente » Cod sursa (job #263134) | Cod sursa (job #370376) | Cod sursa (job #1388353) | Cod sursa (job #167617) | Cod sursa (job #3271056)
#include <unordered_map>
#include <fstream>
#include <vector>
#include <stack>
const int nmax = 1e5;
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, x, y;
vector<int> g[nmax + 1], gt[nmax + 1];
bool visited[nmax + 1];
stack<int> finished;
unordered_map<int, vector<int>> scc;
void dfs(int node, vector<int> graph[], bool collect = true, int scc_index = -1) {
visited[node] = true;
if(scc_index != -1) {
scc[scc_index].push_back(node);
}
for (int child : graph[node]) {
if (!visited[child]) {
dfs(child, graph, collect, scc_index);
}
}
if (collect) {
finished.push(node);
}
}
int kosaraju() {
int scc_count = 0;
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
dfs(i, g);
}
}
fill(visited, visited + n + 1, false);
while (!finished.empty()) {
int node = finished.top();
finished.pop();
if (!visited[node]) {
dfs(node, gt, false, scc_count);
scc_count++;
}
}
return scc_count;
}
int main() {
fin >> n >> m;
while (m--) {
fin >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
fout << kosaraju() << '\n';
for(auto kv: scc) {
for(auto node: kv.second) {
fout << node << ' ';
}
fout << '\n';
}
return 0;
}