Pagini recente » Cod sursa (job #873196) | Cod sursa (job #3230488) | Cod sursa (job #2473262) | Cod sursa (job #1937385) | Cod sursa (job #2888918)
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <fstream>
#include <iostream>
#include <queue>
using std::vector;
using std::string;
using std::ifstream;
using std::ofstream;
using std::set;
using std::pair;
using std::queue;
#define arc pair<int, int>
#define nod first
#define cost second
#define oo 0x3f3f3f3f
class Solve {
private:
string input_file;
string output_file;
vector<int>* graft;
vector<int>* graf;
vector<int> topo;
vector<bool> viz;
vector<vector<int>> result;
int n, m;
void read() {
ifstream in(input_file);
in >> n >> m;
graf = new vector<int>[n + 1];
graft = new vector<int>[n + 1];
viz.resize(n + 1, false);
int x, y;
for (int i = 1; i <= m; ++i) {
in >> x >> y;
graf[x].push_back(y);
graft[y].push_back(x);
}
in.close();
}
void dfs(int node) {
viz[node] = true;
for (const auto& vecin : graf[node]) {
if (!viz[vecin]) {
dfs(vecin);
}
}
topo.push_back(node);
}
void dfst(int node, vector<int>& componenta) {
viz[node] = false;
componenta.push_back(node);
for (const auto& vecin : graft[node]) {
if (viz[vecin]) {
dfst(vecin, componenta);
}
}
}
void solve() {
read();
for (int i = 1; i <= n; ++i) {
if (!viz[i]) {
dfs(i);
}
}
for (vector<int>::reverse_iterator it = topo.rbegin(); it != topo.rend(); ++it) {
if (viz[*it]) {
vector<int> componenta;
dfst(*it, componenta);
result.push_back(componenta);
}
}
}
public:
Solve(const string& input_file, const string& output_file) : input_file{ input_file }, output_file{ output_file }{};
void print() {
ofstream out(output_file);
solve();
out << result.size() << '\n';
for (const auto& componenta : result) {
for (const auto& node : componenta) {
out << node << " ";
}
out << '\n';
}
out.close();
}
~Solve() {
delete[] graf;
}
};
int main() {
Solve s = Solve("ctc.in", "ctc.out");
s.print();
return 0;
}