Pagini recente » Cod sursa (job #2360353) | Cod sursa (job #2073401) | Cod sursa (job #2101513) | Cod sursa (job #2050996) | Cod sursa (job #2925697)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
class Graph {
private:
int _nodes, _edges;
vector<vector<int>> _adj_list;
/*here for convenience*/
int _crt_index = 1;
stack<int> _comp_stack;
vector<vector<int>> _components;
vector<bool> _onStack;
vector<int> _index;
vector<int> _lowlink;
void dfs(const int start){
_index[start] = _crt_index++;
_lowlink[start] = _index[start];
_comp_stack.push(start);
_onStack[start] = true;
for (const auto node : _adj_list[start]) {
if (!_index[node]) {
dfs(node);
}
_lowlink[start] = min(_lowlink[start], _lowlink[node]);
}
if(_lowlink[start]==_index[start]){
vector<int> component;
while (_comp_stack.top() != start){
const int node = _comp_stack.top();
_comp_stack.pop();
_onStack[node] = false;
component.push_back(node);
}
component.push_back(start);
_onStack[start] = false;
_comp_stack.pop();
_components.push_back(move(component));
}
}
public:
Graph(int nodes, int edges, vector<vector<int>> adj_list) :
_nodes(nodes),
_edges(edges),
_adj_list(std::move(adj_list)) {}
vector<vector<int>> stronglyConnected(){
_crt_index = 1;
_onStack = vector<bool>(_nodes+1,false);
_index = vector<int>(_nodes + 1, 0);
_lowlink = vector<int>(_nodes + 1, 0);
for(int node = 1;node<=_nodes;++node){
if(!_index[node]){
dfs(node);
}
}
return _components;
}
};
int main(){
ifstream in("ctc.in");
int nodes, edges;
in >> nodes >> edges;
vector<vector<int>> adj_list(nodes+1);
for(int i=0; i<edges; ++i)
{
int node1, node2;
in >> node1 >> node2;
adj_list[node1].push_back(node2);
}
in.close();
ofstream out("ctc.out");
Graph g(nodes, edges, adj_list);
auto stronglyConnected = g.stronglyConnected();
out << stronglyConnected.size()<<"\n";
for(auto comp : stronglyConnected){
for(auto node : comp){
out << node << " ";
}
out << "\n";
}
}