Pagini recente » Istoria paginii utilizator/6giannac74100hh4 | Cod sursa (job #2087641) | Cod sursa (job #3221844) | Statistici Antighin Alexandru Andrei (itm.Antighin.Alexandru) | Cod sursa (job #2850664)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M;
vector<vector<int>> edges;
vector<vector<int>> inverse_edges;
vector<int> topo;
vector<bool> visited;
vector<vector<int>> scc;
void dfs(int node0) {
visited[node0] = 1;
for(auto node: edges[node0]) {
if(!visited[node]) {
dfs(node);
}
}
topo.push_back(node0);
}
void inverse_dfs(int node0) {
visited[node0] = 1;
scc.back().push_back(node0);
for(auto node: inverse_edges[node0]) {
if(!visited[node]) {
inverse_dfs(node);
}
}
}
int main() {
fin >> N >> M;
edges = vector<vector<int>> (N + 1);
inverse_edges = vector<vector<int>> (N + 1);
for(int i = 1; i <= M; i++) {
int x, y;
fin >> x >> y;
edges[x].push_back(y);
inverse_edges[y].push_back(x);
}
visited = vector<bool> (N + 1, 0);
for(int i = 1; i <= N; i++) {
if(!visited[i]) {
dfs(i);
}
}
visited = vector<bool> (N + 1, 0);
for(int i = (int) topo.size() - 1; i >= 0; i--) {
scc.push_back({});
if(!visited[topo[i]]) {
inverse_dfs(topo[i]);
}
if(scc.back().size() == 0) {
scc.pop_back();
}
}
fout << scc.size() << '\n';
for(int i = 0; i < (int) scc.size(); i++) {
for(int j = 0; j < (int) scc[i].size(); j++) {
fout << scc[i][j] << " ";
}
fout << '\n';
}
return 0;
}