Pagini recente » Cod sursa (job #2452006) | Cod sursa (job #3200027) | Cod sursa (job #130242) | Cod sursa (job #1415932) | Cod sursa (job #2888217)
#include <vector>
#include <string>
#include <fstream>
using std::vector;
using std::string;
using std::ifstream;
using std::ofstream;
class TareConexe {
private:
int n, m;
string input_file, output_file;
vector<int>* graf;
vector<int>* graft;
vector<bool> viz;
vector<int> topo;
vector<vector<int>> result;
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 (auto vecin : graf[node]) {
if (!viz[vecin]) {
dfs(vecin);
}
}
topo.push_back(node);
}
void dfst(int node, vector<int>& componenta) {
componenta.push_back(node);
viz[node] = false;
for (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:
TareConexe(const string& input_file, const string& output_file) : input_file{ input_file }, output_file{ output_file }, topo(), result(){};
void print() {
solve();
ofstream out(output_file);
out << result.size() << '\n';
for (auto componenta : result) {
for (auto node : componenta) {
out << node << " ";
}
out << '\n';
}
out.close();
}
~TareConexe() {
delete[] graf;
delete[] graft;
}
};
int main() {
TareConexe t = TareConexe("ctc.in", "ctc.out");
t.print();
return 0;
}