Pagini recente » Cod sursa (job #2595232) | Cod sursa (job #2826698) | Cod sursa (job #1503735) | Cod sursa (job #363896) | Cod sursa (job #2924540)
#include <fstream>
#include <vector>
using namespace std;
int N, M;
vector <vector <int>> graph, rev_graph;
vector <bool> seen;
vector <int> topo;
vector <vector <int>> answer;
vector <int> aux;
void dfs1(int node) {
seen[node] = true;
for (auto& x : graph[node]) {
if (!seen[x]) {
dfs1(x);
}
}
topo.push_back(node);
}
void dfs2(int node) {
aux.push_back(node);
seen[node] = true;
for (auto& x : rev_graph[node]) {
if (!seen[x]) {
dfs2(x);
}
}
}
int main() {
ifstream fin("ctc.in");
ofstream fout("ctc.out");
fin >> N >> M;
graph = vector<vector<int>>(N, vector<int>());
rev_graph = vector<vector<int>>(N, vector<int>());
seen = vector<bool>(N, false);
for (int i = 0; i < M; ++i) {
int u, v;
fin >> u >> v;
--u; --v;
graph[u].push_back(v);
rev_graph[v].push_back(u);
}
for (int i = 0; i < N; ++i) {
if (!seen[i]) {
dfs1(i);
}
}
seen = vector <bool>(N, false);
for (int i = N - 1; i >= 0; --i) {
if (!seen[topo[i]]) {
aux.clear();
dfs2(topo[i]);
answer.push_back(aux);
}
}
fout << answer.size() << "\n";
for (auto& v : answer) {
for (auto& i : v) {
fout << i + 1 << " ";
}
fout << "\n";
}
fin.close();
fout.close();
return 0;
}