#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
class Graph
{
int NumberOfNodes;
int NumberOfEdges;
bool Oriented;
vector<vector<int>> AdjacencyList;
public:
Graph();
Graph(int, int, bool);
void Build();
void BFS(int, int[]);
void DFS(int, bool[]);
int NumberOfConnectedComponents();
void functionBCC(int, int, int[], int[], stack<int>&, bool[], vector<vector<int>>&);
vector<vector<int>> BiconnectedComponents(int);
};
int main()
{
int NumberOfNodes, NumberOfEdges;
fin >> NumberOfNodes >> NumberOfEdges;
Graph G(NumberOfNodes, NumberOfEdges, 0);
G.Build();
vector<vector<int>> BCCs = G.BiconnectedComponents(0);
fout << BCCs.size() << "\n";
for (unsigned int i = 0; i < BCCs.size(); i++)
{
vector<int> BCC = BCCs[i];
for (unsigned int j = 0; j < BCC.size(); j++)
{
int node = BCC[j] + 1;
fout << node << " ";
}
fout << "\n";
}
/* ----------------------------DFS----------------------------
int NumberOfNodes, NumberOfEdges;
fin >> NumberOfNodes >> NumberOfEdges;
Graph G(NumberOfNodes, NumberOfEdges, 0);
G.Build();
fout << G.NumberOfConnectedComponents();
----------------------------DFS----------------------------*/
/* ----------------------------BFS----------------------------
int NumberOfNodes, NumberOfEdges, StartNode;
fin >> NumberOfNodes >> NumberOfEdges >> StartNode;
Graph G(NumberOfNodes, NumberOfEdges, true);
G.Build();
int Distance[NumberOfNodes];
StartNode--;
G.BFS(StartNode, Distance);
for (int i = 0; i < NumberOfNodes; i++)
fout << Distance[i] << " ";
----------------------------BFS----------------------------*/
fin.close();
fout.close();
return 0;
}
Graph::Graph() : NumberOfNodes(0), NumberOfEdges(0), Oriented(0) { }
Graph::Graph(int _NumberOfNodes, int _NumberOfEdges, bool _Oriented) : NumberOfNodes(_NumberOfNodes), NumberOfEdges(_NumberOfEdges), Oriented(_Oriented)
{
NumberOfNodes = _NumberOfNodes;
NumberOfEdges = _NumberOfEdges;
Oriented = _Oriented;
for (int i = 0; i < _NumberOfNodes; i++)
AdjacencyList.push_back( {} );
//AdjacencyList.push_back(vector<int>());
}
void Graph::Build()
{
for (int i = 0; i < NumberOfEdges; i++)
{
int FirstNode, SecondNode;
fin >> FirstNode >> SecondNode;
FirstNode--;
SecondNode--;
AdjacencyList[FirstNode].push_back(SecondNode);
if (!Oriented)
AdjacencyList[SecondNode].push_back(FirstNode);
}
}
void Graph::BFS(int StartNode, int Distance[])
{
bool Visited[NumberOfNodes];
queue<int> BFSQueue;
for(int i = 0; i < NumberOfNodes; i++)
{
Visited[i] = 0;
Distance[i] = -1;
}
Visited[StartNode] = 1;
Distance[StartNode] = 0;
BFSQueue.push(StartNode);
while (!BFSQueue.empty())
{
int CurrentNode = BFSQueue.front();
for (unsigned int i = 0; i < AdjacencyList[CurrentNode].size(); i++)
{
int AdjacentNode = AdjacencyList[CurrentNode][i];
if (!Visited[AdjacentNode])
{
Visited[AdjacentNode] = 1;
Distance[AdjacentNode] = Distance[CurrentNode] + 1;
BFSQueue.push(AdjacentNode);
}
}
BFSQueue.pop();
}
}
void Graph::DFS(int StartNode, bool Visited[])
{
Visited[StartNode] = 1;
for (unsigned int i = 0; i < AdjacencyList[StartNode].size(); i++) //parcurg vecinii nodului
{
int NextNode = AdjacencyList[StartNode][i];
if (!Visited[NextNode])
DFS(NextNode, Visited);
}
}
int Graph::NumberOfConnectedComponents()
{
bool Visited[NumberOfNodes];
int _NumberOfConnectedComponents = 0;
for (int i = 0; i < NumberOfNodes; i++)
Visited[i] = 0;
for (int i = 0; i < NumberOfNodes; i++)
{
if (!Visited[i])
{
DFS(i, Visited);
_NumberOfConnectedComponents++;
}
}
return _NumberOfConnectedComponents;
}
vector<vector<int>> Graph::BiconnectedComponents(int Node)
{
int id = 0, ids[NumberOfNodes], low[NumberOfNodes];
bool onStack[NumberOfNodes];
vector<vector<int>> BCCs;
stack<int> Stack;
for (int i = 0; i < NumberOfNodes; i++)
onStack[i] = 0;
functionBCC(Node, id, ids, low, Stack, onStack, BCCs);
return BCCs;
}
void Graph::functionBCC(int Node, int id, int ids[], int low[], stack<int> &Stack, bool onStack[], vector<vector<int>> &BCCs)
{
Stack.push(Node);
onStack[Node] = 1;
ids[Node] = low[Node] = id++;
for (unsigned int i = 0; i < AdjacencyList[Node].size(); i++)
{
int AdjacentNode = AdjacencyList[Node][i];
if (onStack[AdjacentNode])
low[Node] = min(low[Node], ids[AdjacentNode]);
else
{
functionBCC(AdjacentNode, id, ids, low, Stack, onStack, BCCs);
low[Node] = min(low[Node], low[AdjacentNode]);
if (low[AdjacentNode] >= ids[Node])
{
vector<int> BCC;
int NodeBCC;
BCC.push_back(Node);
do {
NodeBCC = Stack.top();
BCC.push_back(NodeBCC);
Stack.pop();
} while (NodeBCC != AdjacentNode);
BCCs.push_back(BCC);
}
}
}
}