Pagini recente » Cod sursa (job #2751663) | Profil MarinPeptenaru | Cod sursa (job #2100805) | Cod sursa (job #1388751) | Cod sursa (job #2792556)
#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 (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])
{
vector<int> bicon_comp;
bicon_comp.push_back(current_node);
int node = nodes.back();
nodes.pop_back();
bicon_comp.push_back(node);
while (node != next_node)
{
node = nodes.back();
nodes.pop_back();
bicon_comp.push_back(node);
}
bicon_comps.push_back(bicon_comp);
}
}
else
{
//modify the shortest distance if the node is already visited
shortest_distance[current_node] = min(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 (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] + 1 << " ";
}
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;
}