Pagini recente » Cod sursa (job #1412403) | Cod sursa (job #890394) | Cod sursa (job #2270598) | Cod sursa (job #1876806) | Cod sursa (job #2792535)
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
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 (unsigned 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 find_biconnected_comp(int current_node, int parent_node, int current_distance,
vector<int>& distance, vector<int>& shortest_distance, vector<bool>& visited, vector<int>& nodes, vector<vector<int>>& bicon_comps)
{
distance[current_node] = current_distance;
shortest_distance[current_node] = current_distance;
visited[current_node] = true;
nodes.push_back(current_node);
for (unsigned int i = 0; i < this->adj_list[current_node].size(); i++)
{
int next_node;
next_node = this->adj_list[current_node][i];
if (next_node != parent_node)
{
if (!visited[next_node])
{
find_biconnected_comp(next_node, current_node, current_distance + 1, distance, shortest_distance, visited, nodes, bicon_comps);
shortest_distance[current_node] = min(shortest_distance[current_node], shortest_distance[next_node]);
if (distance[current_node] <= shortest_distance[next_node])
{
/*
if the distance of current node is smaller than or equal
to the shortest distance of the next node,
that means, that the current node is an articulation point
push all the components from nodes to bicon_comp
while popping the nodes
untill we reach the articulation point
*/
vector<int> bicon_comp;
bicon_comp.push_back(current_node);
while (nodes.back() != current_node)
{
bicon_comp.push_back(nodes.back());
nodes.pop_back();
}
bicon_comps.push_back(bicon_comp);
}
}
else
{
//modify the shortest distance if the node is already visited
shortest_distance[current_node] = distance[next_node];
}
}
}
}
void biconnected_components()
{
//setting up all the vectors
vector<vector<int>> bicon_comps;
vector<int> nodes;
vector<bool> visited;
vector<int> distance;
vector<int> shortest_distance;
for (unsigned int i = 0; i < this->n; i++)
{
visited.push_back(false);
distance.push_back(-1);
shortest_distance.push_back(-1);
}
find_biconnected_comp(0, -1, 0, distance, shortest_distance, visited, nodes, bicon_comps);
fout << bicon_comps.size() << endl;
for (unsigned int i = 0; i < bicon_comps.size(); i++)
{
for (unsigned int k = 0; k < bicon_comps[i].size(); k++)
{
fout << bicon_comps[i][k] << " ";
}
fout << endl;
}
}
};
int main()
{
//number of nodes
int N;
//number of edges
int E;
fin >> N >> E;
Graph graph(N, false);
int n1, n2;
for (int i = 0; i < E; i++)
{
fin >> n1 >> n2;
graph.add_edge(n1-1, n2-1);
}
graph.biconnected_components();
return 0;
}