Pagini recente » Cod sursa (job #206518) | Cod sursa (job #2102231) | Cod sursa (job #1298873) | Cod sursa (job #2887947) | Cod sursa (job #2814036)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define Max 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int N, M;
bool visited[Max];
int up[Max], levels[Max];
int Stack[Max], top;
vector<int> biconnected_components[Max];
int number_of_biconnected_components;
class Graph{
private:
int NumberOfNodes, NumberOfEdges;
vector<int> adjacencyList[Max];
public:
Graph(int N, int M); // constructor
void Read_UndirectedGraph();
void DFS_BiconnectedComponents(int, int);
void Write_BiconnectedComponents();
};
// constructor
Graph :: Graph(int N, int M)
{
NumberOfNodes = N;
NumberOfEdges = M;
}
void Graph :: Read_UndirectedGraph()
{
for ( int i = 1; i <= NumberOfEdges; i++ )
{
int x, y;
fin >> x >> y;
adjacencyList[x].push_back(y);
adjacencyList[y].push_back(x);
}
}
void Graph :: DFS_BiconnectedComponents(int node, int parent )
{
visited[node] = 1;
up[node] = levels[node];
Stack[++top] = node; // adaugam nodul in stiva
for ( auto i : adjacencyList[node] )
{
if ( i == parent ) continue;
if ( visited[i] )
up[node] = min(up[node], levels[i]);
else
{
levels[i] = levels[node] + 1;
DFS_BiconnectedComponents(i, node);
if ( up[i] >= levels[node] )
{
number_of_biconnected_components++;
while ( top && Stack[top] != i )
biconnected_components[number_of_biconnected_components].push_back(Stack[top--]);
biconnected_components[number_of_biconnected_components].push_back(Stack[top--]);
biconnected_components[number_of_biconnected_components].push_back(node);
}
up[node] = min(up[node], up[i]);
}
}
}
void Graph :: Write_BiconnectedComponents()
{
int j;
fout << number_of_biconnected_components << "\n";
for ( int i = 1; i <= number_of_biconnected_components; i++ )
{
for ( auto j : biconnected_components[i] )
fout << j << " ";
fout << "\n";
}
}
int main()
{
fin >> N >> M;
Graph G(N, M);
G.Read_UndirectedGraph();
G.DFS_BiconnectedComponents(1, 0);
G.Write_BiconnectedComponents();
return 0;
}