Pagini recente » Monitorul de evaluare | Cod sursa (job #823425) | Cod sursa (job #1320679) | Cod sursa (job #523077) | Cod sursa (job #2796471)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
class Graph {
private:
int _n, _m;
vector<int> _list[100001];
int viz[100001];
public:
Graph(int nodes, int edges) : _n(nodes), _m(edges) {}
void addEdges();
void dfs_ctc(int node, vector<int> &ordine);
void transpose();
vector<vector<int>> ctc();
};
void Graph::addEdges() {
int x, y, i;
for (i = 0; i < _m; i++) {
f >> x >> y;
_list[x].push_back(y);
}
}
//graful transpus
void Graph::transpose() {
vector<int> transp_edges[_n + 1];
int i, j;
for (i = 1; i <= _n; i++)
for (j = 0; j < _list[i].size(); j++)
transp_edges[_list[i][j]].push_back(i);
for (i = 1; i <= _n; i++) {
_list[i] = transp_edges[i];
}
}
void Graph::dfs_ctc(int node, vector<int> &ordine) {
viz[node] = 1;
for (int i = 0; i < _list[node].size(); i++) {
if (!viz[_list[node][i]])
dfs_ctc(_list[node][i], ordine);
}
//in ordine pastrez nodurile cand sunt finalizate de dfs
ordine.push_back(node);
}
vector<vector<int>> Graph::ctc() {
vector<vector<int>> ans;
vector<int> ordine;
for (int i = 1; i <= _n; i++){
if (!viz[i]) {
dfs_ctc(i, ordine);
}
}
//inversez ordinea
reverse(ordine.begin(), ordine.end());
//fac graful transpus
transpose();
//resetez vectorul de vizitari
for (int i = 1; i <= _n; i++)
viz[i] = 0;
//fac dfs pentru elemente din ordine (cele inversate)
for (int i = 0; i < _n; i++) {
if (!viz[ordine[i]]) {
vector<int> v;
dfs_ctc(ordine[i], v);
ans.push_back(v);
}
}
return ans;
}
int main() {
int n, m;
f >> n >> m;
Graph gr(n, m);
gr.addEdges();
vector<vector<int>> ans = gr.ctc();
cout << ans.size() << '\n';
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < ans[i].size(); j++)
g << ans[i][j] << " ";
g << '\n';
}
f.close();
g.close();
return 0;
}