#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");
class Graph
{
private:
bool m_oriented;
int m_nrNodes;
int m_nrEdges;
vector <int> m_nodes;
vector < vector <int> > m_neighborList;
void BFS(vector<bool>& visitedNodes, vector<int>& distances, int startNode = 0);
void DFS(vector<bool>& visitedNodes, int currentNode = 0);
void BCDFS(vector< vector <int> >& bcc, stack<int>& nodeStack, vector<bool>& visited, vector<int>& depth, vector<int>& lowestDepthReacheable, int currentNode, int parentNode, int currentDepth);
void TDFS(vector< vector <int> >& scc, stack<int>& nodeStack, vector<bool>& stackMember, vector<int>& discoveryOrder, vector<int>& lowestDepthReacheable, int currentNode, int& currentTime);
void TDFS_criticalConnections(vector< vector<int> >& solution, stack<int>& nodeStack, vector<int>& discoveryOrder, vector<int>& lowestDepthReacheable, int currentNode, int parentNode, int& currentTime);
public:
Graph(int nrNodes = 0, int nrEdges = 0, bool oriented = false);
~Graph() {}
#pragma region Setters&Getters
void setOrientation(bool orientation)
{
m_oriented = orientation;
}
void setNrNodes(int nrNodes)
{
m_nrNodes = nrNodes;
}
void setNrEdges(int nrEdges)
{
m_nrEdges = nrEdges;
}
bool getOrientation()
{
return m_oriented;
}
int getNrNodes()
{
return m_nrNodes;
}
int getNrEdges()
{
return m_nrEdges;
}
#pragma endregion
void buildNeighborList(istream& input);
vector<int> minimalDistances(int startNode);
int numberOfConexComponents();
vector< vector <int> > BiconnectedComponents();
vector< vector <int> > StronglyConnectedComponents();
vector<vector<int>> criticalConnections();
vector<int> minimalDistanceBetweenTwoNodes(int startNode, int finishNode);
};
Graph::Graph(int nrNodes, int nrEdges, bool oriented)
{
m_nrNodes = nrNodes;
m_nrEdges = nrEdges;
m_oriented = oriented;
for (int i = 0; i < nrNodes; i++)
{
vector <int> emptyVector;
m_neighborList.push_back(emptyVector);
}
}
void Graph::buildNeighborList(istream& input)
{
for (int i = 0; i < m_nrEdges; i++)
{
int node1, node2;
input >> node1 >> node2;
node1--;
node2--;
m_neighborList[node1].push_back(node2);
if (m_oriented == false)
{
m_neighborList[node2].push_back(node1);
}
}
}
void Graph::BFS(vector<bool>& visitedNodes, vector<int>& distances, int startNode)
{
queue<int> nodeOrder;
nodeOrder.push(startNode);
distances[startNode] = 0;
while (nodeOrder.empty() == false)
{
int currentNode = nodeOrder.front();
visitedNodes[currentNode] = true;
for (auto neighbor : m_neighborList[currentNode])
{
if (visitedNodes[neighbor] == false)
{
nodeOrder.push(neighbor);
distances[neighbor] = distances[currentNode] + 1;
visitedNodes[neighbor] = true;
}
}
nodeOrder.pop();
}
}
void Graph::DFS(vector<bool>& visitedNodes, int currentNode)
{
visitedNodes[currentNode] = true;
for (auto neighbor : m_neighborList[currentNode])
{
if (visitedNodes[neighbor] == false)
{
DFS(visitedNodes, neighbor);
visitedNodes[neighbor] = true;
}
}
}
void Graph::BCDFS(vector< vector <int>>& bcc, stack<int>& nodeStack, vector<bool>& visited, vector<int>& depth, vector<int>& lowestDepthReacheable, int currentNode, int parentNode, int currentDepth)
{
depth[currentNode] = currentDepth; //initializing the depth of the current node
lowestDepthReacheable[currentNode] = currentDepth; //initializing the lowest depth reacheble time of the current node
visited[currentNode] = true; //insert the current node in the stack and mark it as visited
nodeStack.push(currentNode);
for (auto neighbor : m_neighborList[currentNode])
{
if (neighbor != parentNode)
{
if (visited[neighbor] == true)
{
lowestDepthReacheable[currentNode] = min(lowestDepthReacheable[currentNode], depth[neighbor]); //this is were the back edges are found
}
else
{
BCDFS(bcc, nodeStack, visited, depth, lowestDepthReacheable, neighbor, currentNode, currentDepth + 1);
lowestDepthReacheable[currentNode] = min(lowestDepthReacheable[currentNode], lowestDepthReacheable[neighbor]); //updating with lowest depth that the descendants can reach
if (depth[currentNode] <= lowestDepthReacheable[neighbor]) //if it is true it means that the neighbor has no back edge above the current node
{ //current node separates two biconnected components
vector <int> biconnectedComponent;
biconnectedComponent.push_back(currentNode);
int node = nodeStack.top();
nodeStack.pop();
biconnectedComponent.push_back(node);
while (node != neighbor) //pop nodes until we reach the neighbor (inclusive) and that is the current biconnected component
{
node = nodeStack.top();
nodeStack.pop();
biconnectedComponent.push_back(node);
}
bcc.push_back(biconnectedComponent); //adding it to the rest of the components
}
}
}
}
}
void Graph::TDFS(vector< vector <int> >& scc, stack<int>& nodeStack, vector<bool>& stackMember, vector<int>& discoveryOrder, vector<int>& lowestDepthReacheable, int currentNode, int& currentTime)
{
discoveryOrder[currentNode] = currentTime; //initializing the discovery time of the current node
lowestDepthReacheable[currentNode] = currentTime; //initializing the lowest depth reacheble time of the current node
stackMember[currentNode] = true; //insert the current node in the stack and mark it
nodeStack.push(currentNode);
currentTime++; //increment the time
for (auto neighbor : m_neighborList[currentNode]) //visit all neibors
{
if (discoveryOrder[neighbor] == -1) //if it has not been visited yet
{
TDFS(scc, nodeStack, stackMember, discoveryOrder, lowestDepthReacheable, neighbor, currentTime); //DFS on that node
lowestDepthReacheable[currentNode] = min(lowestDepthReacheable[currentNode], lowestDepthReacheable[neighbor]); //actualizing on the recursion return path
}
else if (stackMember[neighbor] == true) //if the neighbor is on the stack is part of the current strongly connected component
{
lowestDepthReacheable[currentNode] = min(lowestDepthReacheable[currentNode], discoveryOrder[neighbor]);
}
}
if (lowestDepthReacheable[currentNode] == discoveryOrder[currentNode]) //if lowestDepthReacheable and discoveryOrder are equal it means the current node is the root of
{ //the current strongly connected component
vector <int> stronglyConnectedComponent;
int node = nodeStack.top();
nodeStack.pop();
stackMember[node] = false;
stronglyConnectedComponent.push_back(node);
while (node != currentNode) //pop nodes until we reach current node (inclusive) and that is the current strongly connected component
{
node = nodeStack.top();
nodeStack.pop();
stackMember[node] = false;
stronglyConnectedComponent.push_back(node);
}
scc.push_back(stronglyConnectedComponent); //adding it to the rest of the components
}
}
void Graph::TDFS_criticalConnections(vector< vector<int> >& solution, stack<int>& nodeStack, vector<int>& discoveryOrder, vector<int>& lowestDepthReacheable, int currentNode, int parentNode, int& currentTime)
{
discoveryOrder[currentNode] = currentTime;
lowestDepthReacheable[currentNode] = currentTime;
nodeStack.push(currentNode);
currentTime++;
for (auto neighbor : m_neighborList[currentNode])
{
if (discoveryOrder[neighbor] == -1)
{
TDFS_criticalConnections(solution, nodeStack, discoveryOrder, lowestDepthReacheable, neighbor, currentNode, currentTime);
lowestDepthReacheable[currentNode] = min(lowestDepthReacheable[currentNode], lowestDepthReacheable[neighbor]);
if (lowestDepthReacheable[neighbor] > discoveryOrder[currentNode])
{
vector <int> result;
result.push_back(currentNode);
result.push_back(neighbor);
solution.push_back(result);
}
}
else if (neighbor != parentNode)
{
lowestDepthReacheable[currentNode] = min(lowestDepthReacheable[currentNode], discoveryOrder[neighbor]);
}
}
if (lowestDepthReacheable[currentNode] == discoveryOrder[currentNode])
{
int node = nodeStack.top();
nodeStack.pop();
while (node != currentNode)
{
node = nodeStack.top();
nodeStack.pop();
}
}
}
vector<int> Graph::minimalDistances(int startNode)
{
vector <bool> visited(m_nrNodes, false);
vector <int> distances(m_nrNodes, -1);
BFS(visited, distances, startNode);
return distances;
}
int Graph::numberOfConexComponents()
{
int numberOfConexComponents = 0;
vector <bool> visited(m_nrNodes, false);
for (int i = 0; i < m_nrNodes; i++)
{
if (visited[i] == false)
{
DFS(visited, i);
numberOfConexComponents++;
}
}
return numberOfConexComponents;
}
vector< vector <int> > Graph::BiconnectedComponents() //initializing all data structures needed for the Biconnected DFS Algorithm
{
vector< vector<int> > bcc; //this will contain all Biconnected Components
stack<int> nodeStack; //will store the connected ancestors
vector<bool> visited(m_nrNodes, false); //will check whether a node has been visited or not
vector<int> depth(m_nrNodes, -1); //will cotain the depth of every node
vector<int> lowestDepthReacheable(m_nrNodes, -1); //will contain the lowest depth a node can reach through its descendants
BCDFS(bcc, nodeStack, visited, depth, lowestDepthReacheable, 0, -1, 0);
return bcc;
}
vector< vector <int> > Graph::StronglyConnectedComponents() //initializing all data structures needed for the Tarjan's DFS Algorithm
{
vector< vector<int> > scc; //this will contain all Strongly Connected Components
stack<int> nodeStack; //will store the connected ancestors
vector<bool> stackMember(m_nrNodes, false); //will check whether a node is in stack
vector<int> discoveryOrder(m_nrNodes, -1); //contains the order in which the nodes are dicovered
vector<int> lowestDepthReacheable(m_nrNodes, -1); //the lowest ancestor that can be reached
int currentTime = 0; //a timer used for discoveryOrder and lowestDepthReacheable
for (int i = 0; i < m_nrNodes; i++)
{
if (discoveryOrder[i] == -1) //if the node hasn't been discovered yet, we start the DFS from him
{
TDFS(scc, nodeStack, stackMember, discoveryOrder, lowestDepthReacheable, i, currentTime); //the tarjan's algorithm
}
}
return scc;
}
vector<vector<int>> Graph::criticalConnections()
{
vector< vector<int> > solution;
vector<int> discoveryOrder(m_nrNodes, -1);
vector<int> lowestDepthReacheable(m_nrNodes, -1);
stack<int> nodeStack;
int currentTime = 0;
for (int i = 0; i < m_nrNodes; i++)
{
if (discoveryOrder[i] == -1)
{
TDFS_criticalConnections(solution, nodeStack, discoveryOrder, lowestDepthReacheable, i, -1, currentTime);
}
}
return solution;
}
vector<int> Graph::minimalDistanceBetweenTwoNodes(int startNode, int finishNode)
{
vector<int> normalWay(m_nrNodes, -1); //will contain the values from the bfs starting from the starting node
vector<int> reverseWay(m_nrNodes, -1); //will contain the values from the bfs starting from the finishing node
vector<int> frequency(m_nrNodes, 0); //will contain the frequency of the nodes, if a node is on all of the minimal ways between the starting node and the finishing node,
vector<int> result; //then his distance will be the same from those nodes
normalWay = minimalDistances(startNode); //getting the minimal distances in the normal way
reverseWay = minimalDistances(finishNode); //getting the minimal distances in the reverse way
int minimWay = normalWay[finishNode]; //the minimal distance between the starting node and the finishing node
for (int i = 0; i < m_nrNodes; i++)
if (normalWay[i] + reverseWay[i] == minimWay)
frequency[normalWay[i]]++;
for (int i = 0; i < m_nrNodes; i++)
if (normalWay[i] + reverseWay[i] == minimWay && frequency[normalWay[i]] == 1)
result.push_back(i);
return result;
}
int main()
{
int nrNodes, nrEdges;
vector< vector<int> > bcc;
fin >> nrNodes >> nrEdges;
Graph graph(nrNodes, nrEdges, false);
graph.buildNeighborList(fin);
bcc = graph.BiconnectedComponents();
fout << bcc.size() << "\n";
for (int i = 0; i < bcc.size(); i++)
{
for (auto node : bcc[i])
{
fout << node + 1 << " ";
}
fout << "\n";
}
fin.close();
fout.close();
return 0;
}