Pagini recente » Cod sursa (job #2350485) | Cod sursa (job #2573482) | Cod sursa (job #1807436) | Cod sursa (job #2325451) | Cod sursa (job #2792897)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
//Graph class, all the nodes start from 0
class Graph
{
private:
//number of nodes
int n;
//number of edges
int e;
//bool if graph is oriented
bool oriented;
//adj list for graph representation
vector<vector<int>> adj_list;
public:
Graph(int n, bool oriented)
{
this->n = n;
this->e = 0;
this->oriented = oriented;
//populate adj list with empty vectors
vector<int> empty;
for (int i = 0; i < n; i++)
{
this->adj_list.push_back(empty);
}
}
virtual ~Graph() {}
void add_edge(int node1, int node2)
{
this->e++;
this->adj_list[node1].push_back(node2);
//if graph is not oriented, then push from the second node
if (!this->oriented)
{
this->adj_list[node2].push_back(node1);
}
}
void sccdfs(int current_node, int &id, stack<int> &stck, vector<bool> &on_stack, vector<int> &ids, vector<int> &low_link_values, vector<vector<int>> &str_con_comps)
{
stck.push(current_node);
on_stack[current_node] = true;
ids[current_node] = id;
low_link_values[current_node] = id;
id++;
for (unsigned int i = 0; i < this->adj_list[current_node].size(); i++)
{
int neighbour;
neighbour = adj_list[current_node][i];
if (ids[neighbour] == -1)
{
sccdfs(neighbour, id, stck, on_stack, ids, low_link_values, str_con_comps);
}
if (on_stack[neighbour])
{
low_link_values[current_node] = min(low_link_values[current_node], low_link_values[neighbour]);
}
}
if (ids[current_node] == low_link_values[current_node])
{
vector<int> str_con_comp;
int node = stck.top();
while (node != current_node)
{
str_con_comp.push_back(node);
stck.pop();
on_stack[node] = false;
low_link_values[node] = ids[current_node];
node = stck.top();
}
str_con_comp.push_back(current_node);
stck.pop();
str_con_comps.push_back(str_con_comp);
}
}
void strongly_connected_components()
{
//used to give each node an id
int id = 0;
int scc_count;
vector<int> ids(this->n, -1);
vector<int> low_link_values(this->n, 0);
vector<bool> on_stack(this->n, false);
stack<int> stck;
vector<vector<int>> str_con_comps;
for (int i = 0; i < this->n; i++)
{
if (ids[i] == -1)
{
sccdfs(i, id, stck, on_stack, ids, low_link_values, str_con_comps);
}
}
if (!stck.empty())
{
scc_count = stck.size() + str_con_comps.size();
}
else
{
scc_count = str_con_comps.size();
}
fout << scc_count << "\n";
for (unsigned int i = 0; i < str_con_comps.size(); i++)
{
for (unsigned int k = 0; k < str_con_comps[i].size(); k++)
{
fout << str_con_comps[i][k] + 1 << " ";
}
fout << "\n";
}
while (!stck.empty())
{
int nd = stck.top();
fout << nd << "\n";
stck.pop();
}
}
};
int main()
{
//number of nodes
int N;
//number of edges
int E;
fin >> N >> E;
Graph graph(N, true);
int n1, n2;
for (int i = 0; i < E; i++)
{
fin >> n1 >> n2;
graph.add_edge(n1 - 1, n2 - 1);
}
graph.strongly_connected_components();
return 0;
}