Pagini recente » Cod sursa (job #1110645) | Cod sursa (job #2273172) | Cod sursa (job #72180) | Cod sursa (job #771434) | Cod sursa (job #2788997)
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <queue>
#include <unordered_set>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct Tracker {
int discovery_time;
int lowest_reachable;
Tracker(int d = 0, int l = 0) :discovery_time(d), lowest_reachable(l) { }
};
class Graph {
private:
//Variabile private
int vertices;
int edges;
bool oriented;
vector<int>* adjacency_list;
//To compute:
vector<vector<int>> biconnected_components;
//Functii private
void BFS(int starting_vertex, int* distances);
void DFS(int vertex, int* visited);
void BCC(int vertex, vector<int>& parent, stack<int>& vertices_stack, vector<Tracker>& tracker, int& timer);
public:
Graph(int vertices = 0, int edges = 0, bool oriented = false);
~Graph();
void infoarena_graph();
void show_my_graph();
void solve_distances(int starting_vertex);
void solve_connected_components();
void solve_biconnected();
};
int main() {
int N, M;
fin >> N >> M;
Graph g(N, M, false);
g.infoarena_graph();
g.solve_biconnected();
}
#pragma region Initialization
Graph::Graph(int vertices, int edges, bool oriented) : vertices(vertices), edges(edges), oriented(oriented) {
adjacency_list = new vector<int>[vertices + 1];
}
Graph::~Graph() {
delete[] adjacency_list;
}
void Graph::infoarena_graph() {
int x, y;
if (oriented) {
for (int i = 1; i <= edges; i++) {
fin >> x >> y;
adjacency_list[x].push_back(y);
}
}
else {
for (int i = 1; i <= edges; i++) {
fin >> x >> y;
adjacency_list[x].push_back(y);
adjacency_list[y].push_back(x);
}
}
}
void Graph::show_my_graph() {
for (int i = 1; i < vertices + 1; i++) {
cout << i << "=>";
for (int j : adjacency_list[i]) {
cout << j << ' ';
}
cout << '\n';
}
}
#pragma endregion
//Algorithm implementations
#pragma region Algorithms
void Graph::BFS(int starting_vertex, int* distances) {
int* visited = (int*)calloc(vertices + 1, sizeof(int));
queue<int> que;
que.push(starting_vertex);
distances[starting_vertex] = 1;
visited[starting_vertex] = 1;
while (!que.empty()) {
int current_node = que.front();
que.pop();
for (auto neighbor : adjacency_list[current_node]) {
if (!visited[neighbor]) {
que.push(neighbor);
visited[neighbor] = 1;
distances[neighbor] = distances[current_node] + 1;
}
}
}
free(visited);
}
void Graph::DFS(int vertex, int* visited) {
visited[vertex] = 1;
for (auto neighbor : adjacency_list[vertex])
if (!visited[neighbor])
DFS(neighbor, visited);
}
void Graph::BCC(int vertex, vector<int>& parent, stack<int>& vertices_stack, vector<Tracker>& tracker, int& timer) {
tracker[vertex].discovery_time = tracker[vertex].lowest_reachable = ++timer;
for(auto neighbor : adjacency_list[vertex]){
if(parent[neighbor] != vertex){
vertices_stack.push(vertex);
if(parent[neighbor] == -1){
parent[neighbor] = vertex;
BCC(neighbor,parent,vertices_stack,tracker,timer);
tracker[vertex].lowest_reachable = min(tracker[vertex].lowest_reachable, tracker[neighbor].lowest_reachable);
if(tracker[neighbor].lowest_reachable >= tracker[vertex].discovery_time){
biconnected_components.push_back(vector<int>());
vector<bool> pushed(vertices+1,false);
int n = biconnected_components.size();
int aux = vertices_stack.top();
while(aux!=vertex){
if(!pushed[aux]) {
biconnected_components[n - 1].push_back(aux);
pushed[aux] = true;
}
vertices_stack.pop();
aux = vertices_stack.top();
}
biconnected_components[n-1].push_back(vertex);
}
}
else{
tracker[vertex].lowest_reachable = min(tracker[neighbor].discovery_time, tracker[vertex].lowest_reachable);
}
}
}
}
#pragma endregion
//infoarena solutions
#pragma region Solutions
//Minimal distances BFS problem
void Graph::solve_distances(int starting_vertex) {
int* distances = (int*)calloc(vertices + 1, sizeof(int));
BFS(starting_vertex, distances);
for (int i = 1; i < vertices + 1; i++)
fout << distances[i] - 1 << ' ';
free(distances);
}
//Connected compontents DFS problem
void Graph::solve_connected_components() {
int counter = 0;
int* visited = (int*)calloc(vertices + 1, sizeof(int));
for (int i = 1; i < vertices + 1; i++)
if (!visited[i]) {
DFS(i, visited);
counter++;
}
fout << counter;
free(visited);
}
void Graph::solve_biconnected() {
stack<int> vertices_stack;
vector<int> parent(vertices + 1, -1);
vector<Tracker> tracker(vertices + 1);
int timer = 0;
for (int i = 1; i < vertices + 1; i++) {
if (parent[i] == -1) {
parent[i] = i;
BCC(i, parent, vertices_stack, tracker, timer);
}
}
int num = biconnected_components.size();
fout <<num<< '\n';
for (int i = 0;i<num;i++) {
for (int j=0;j<biconnected_components[i].size();j++)
fout << biconnected_components[i][j] << ' ';
fout << '\n';
}
}
#pragma endregion