#include <bits/stdc++.h>
#define N 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
queue<int> q;
int ctComponents = 0;
vector<int> comp[N]; //to print the strongly connected components
class Graph {
private:
int n, m;
vector<int> adlist[N];
bool viz[N] = {0};
int dist[N] = {0};
stack<int> s; //final times in dfs
void df(int node, bool visited[], int level[], int min_level[],vector<vector<int>> sol); // dfs for critical edges
void dfBiconnected(int k, int father, int level[N], int level_min[N], bool visitedBC[N], vector<set<int>> &biconnected, stack<int> &elem);
//void component(int vertex, int node, vector<set<int>> biconnected, stack< pair <int, int>> edges);
public:
Graph() = default;
Graph(int n, int m):n(n), m(m){}
void readDirected();
void readUndirected();
void bfs(int first); //for minimum path
void dfs(int first); //for connected components
void dfsT(int first); //used only for Transpoused --> do not add nodes in s, print the node
//we will use "viz" from the transpoused graph
void printDist();
void connectedComponents();
void printGraph();
Graph transpose();
void stronglyConnectedComponents();
void sortTopo(); //dfs and we keep the final times, after a node is finished, we put it in the stack
bool graphExistsHakimi(vector<int> &dg, int n); //the grades and number of nodes
void biconnectedComponents();
vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections); /*Input: n = 2, connections = [[0,1]] Output: [[0,1]]*/
};
void Graph::readDirected() {
for(int i = 1; i <= m; ++i) {
int x, y;
fin >> x >> y;
adlist[x].push_back(y);
}
}
void Graph::readUndirected() {
for(int i = 1; i <= m; ++i) {
int x, y;
fin >> x >> y;
adlist[x].push_back(y);
adlist[y].push_back(x);
}
}
void Graph::printGraph() {
for(int i = 1; i <= n; ++i) {
fout << i <<":";
for(int j = 0; j < adlist[i].size(); ++j)
fout << adlist[i][j] << " ";
fout <<"\n";
}
}
void Graph::bfs(int first) {
int node, dim;
dist[first] = 1;
viz[first] = 1;
q.push(first);
while(!q.empty())
{
node = q.front();
q.pop();
dim = adlist[node].size();
for(int i = 0; i < dim; ++i)
if(!viz[adlist[node][i]])
{
fout << adlist[node][i] <<" ";
viz[adlist[node][i]] = 1;
dist[adlist[node][i]] = dist[node] + 1;
q.push(adlist[node][i]);
}
}
}
void Graph::dfs(int node){
int i, dim;
viz[node] = 1;
dim = adlist[node].size();
for(i = 0; i < dim; ++i)
if(!viz[adlist[node][i]])
dfs(adlist[node][i]);
s.push(node);
}
void Graph::dfsT(int node){
int i, dim;
comp[ctComponents].push_back(node);//is part of the same component
viz[node] = 1;
dim = adlist[node].size();
for(i = 0; i < dim; ++i)
if(!viz[adlist[node][i]])
dfsT(adlist[node][i]);
}
void Graph::printDist(){
int i;
for(i = 1; i <= n; ++i)
fout << dist[i] - 1 << " ";
}
void Graph::connectedComponents() {
int i, nr = 0;
for(i = 1; i <= n; ++i)
if(!viz[i])
{
nr++;
dfs(i);
}
fout << nr;
}
Graph Graph::transpose() {
int i, j;
Graph gt(n, m);
for(i = 1; i <= n; ++i)
for(j = 0; j < adlist[i].size(); ++j)
gt.adlist[adlist[i][j]].push_back(i);
return gt;
}
void Graph::stronglyConnectedComponents(){
int node;
for(int i = 1; i <= n; ++i)
if(!viz[i])
this->dfs(i);
Graph gt = this->transpose();
while(!s.empty())
{
node = s.top();
s.pop();
if(!gt.viz[node])
{
ctComponents++;
gt.dfsT(node);
}
}
int i, j;
fout << ctComponents << "\n";
for(i = 1; i <= ctComponents; ++i) {
for(j = 0; j < comp[i].size(); ++j)
fout <<comp[i][j] << " ";
fout << "\n";
}
}
void Graph::sortTopo(){
for(int i = 1; i <= n; ++i)
if(!viz[i])
dfs(i);
while(!s.empty())
{
fout << s.top() <<" ";
s.pop();
}
}
bool Graph::graphExistsHakimi(vector<int> &dg, int n) {
///sort the vector of degrees desc
///we start with the biggest degree v ant link it with the next v nodes (substract 1 from the next v elements)
///repeat until:
///1. all the remaining elements are 0 (graph exists)
///2. negative values encounter after substraction (doesn't exist)
///3. not enough elements remaining after substraction (doesn't exist)
while(1)
{
sort(dg.begin(), dg.end(), greater<>());
if(dg[0] == 0)
return true; //all elements equal to 0
int degree = dg[0];
dg.erase(dg.begin() + 0);
if(degree > dg.size())//check if enough elements are in the list
return false;
for(int i = 0; i < dg.size(); ++i)
{
dg[i]--;
//check negative
if(dg[i] < 0)
return false;
}
}
}
//https://cppsecrets.com/users/100451121149711897108108105107974849505152535455565764103109971051084699111109/C00-Bridges-in-a-graph.php
void Graph::df(int node, bool visited[], int level[], int level_min[], vector<vector<int>> sol) {
/*
level_min[i] = min { level[i], A, B }
○ A = min { level[k] | ik return edge }
○ B = min { level[k] | j is i's descendant, jk return edge }
*/
static int time = 1;//the time that current node was discovered in dfs
visited[node] = 1;
level[node] = level_min[node] = time++;
for(int i = 0; i < adlist[node].size(); ++i) //for each neighbour
if(!visited[adlist[node][i]])///forward edge
{
int current = adlist[node][i];
level[current] = level[i] + 1;
df(current, visited, level, level_min,sol);//continue df from this node
level_min[node] = min(level_min[current], level_min[node]);//B case--> a child has a back edge
if(level_min[current] > level[node])//condtion for critical edge
{
vector<int> v;
v.push_back(node);
v.push_back(current);
sol.push_back(v);
}
}
else ///we have connection to a node that has already been visited ---> have to check if it is on a higher level
{
int current = adlist[node][i];
if(level[current] < level[node] - 1)//it's a return edge, and it is not the father
level_min[node] = min(level_min[node], level[current]);
}
}
vector<vector<int>> Graph :: criticalConnections(int n, vector<vector<int>>& connections) {
for(int i = 0; i < connections.size(); ++i)//for each edge
{
adlist[connections[i][0]].push_back(connections[i][1]);
adlist[connections[i][1]].push_back(connections[i][0]);
}
vector<vector<int>> sol;//solution of critical edges
bool visited[N] = {0};
int level[N] = {0}; //the level of a node in dfs
int level_min[N] = {0}; //the minimum level that can rich with a back edge(if possible)
for(int i = 1; i <= n; ++i)
if(!visited[i])
df(i, visited, level, level_min, sol);
return sol;
}
/*
void Graph::biconnectedComponents(){
///keep adding edges in stack from df tree and when an articulation node is detected
///i.e a vertex u has a child v (level_min[v] >= level[u]) --> has no return edge in the subtree
///pop all edges from the stack till u-v is found ---> all those edges, including u-v will form a biconnected component
bool visitedBC[N] = {0};
int level[N] = {0};
int level_min[N] = {0};
vector<set<int>> biconnected; //bcs we want to add nodes based on component's edges
stack< pair <int, int>> edges; //stack with the edges for df tree
for(int i = 1; i <= n; ++i)
if(!visitedBC[i])
dfBiconnected(i, 0, level, level_min, visitedBC, biconnected, edges);
set<int, greater<int> >::iterator itr; //for looping a set
set<int> s1;
fout << biconnected.size() << "\n";
for(int i = 0; i < biconnected.size(); ++i)
{
s1 = biconnected[i];
for (itr = s1.begin(); itr != s1.end(); itr++)
cout << *itr<<" ";
fout << "\n";
}
for(int i = 1; i <= n; ++i)cout <<level[i] <<" ";
cout <<"\n";
for(int i = 1; i <= n; ++i)cout <<level_min[i] <<" ";
}
void Graph::component(int vertex, int node, vector<set<int>> biconnected, stack< pair <int, int>> edges){
//cout << vertex << " " << node <<"\n";
int x, y;
set<int> comp; //the current component
do
{
pair <int, int> p = edges.top();
x = p.first;
y = p.second;
cout << x << " " << y <<"\n";
edges.pop();
comp.insert(x);
comp.insert(y);
}while(x != vertex || y != node);
cout <<"\n";
biconnected.push_back(comp); //add at the biconnected components
}
void Graph::dfBiconnected(int vertex, int father, int level[N], int level_min[N], bool visitedBC[N], vector<set<int>> biconnected, stack< pair <int, int>> edges){
static int time = 1;
visitedBC[vertex] = 1;
level[vertex] = time++;
level_min[vertex] = level[vertex];
int dim = adlist[vertex].size();
for(int i = 0; i < dim ; ++i)
{
int node = adlist[vertex][i];
if(!visitedBC[node])
{
edges.push({vertex, node}); //add the edge in the stack
dfBiconnected(node, vertex, level, level_min, visitedBC, biconnected, edges); //continue the dfs from here
if(level_min[vertex] > level_min[node] ) //with the current node we can reach a higher level
level_min[vertex] = level_min[node];
if(level[vertex] <= level_min[node]) //it's articulation point
component(vertex, node, biconnected, edges);
}
else //it's a return edge
{
if(node != father)
{
//it means that is a child that has been already visited (level[vertex] < level[node])
//compare level_min[vertex], level[node] to see if using this node we can go to a higer level
if(level_min[vertex] > level[node])
level_min[vertex] = level[node];
}
}
}
}*/
void Graph::biconnectedComponents(){
///keep adding nodes in the stack until we finish the biconnected component
int level[N] = {0};
int level_min[N] = {0};
bool visitedBC[N] = {0};
vector<set<int>> biconnected;//vector with the components
stack<int> elem;// the vertex visited in dfs
dfBiconnected(1, 0, level, level_min, visitedBC,biconnected,elem);
fout << biconnected.size() <<"\n";
set<int, greater<int> >::iterator itr; //for looping a set
for(int i = 0; i < biconnected.size(); i++)
{
set<int> s1 = biconnected[i];
for (itr = s1.begin(); itr != s1.end(); itr++)
fout << *itr<<" ";
fout <<"\n";
}
}
void Graph::dfBiconnected(int k, int father, int level[N], int level_min[N], bool visitedBC[N], vector<set<int>> &biconnected, stack<int> &elem){
visitedBC[k] = 1;
elem.push(k);
level[k] = level[father] + 1;
level_min[k] = level[k];
int dim = adlist[k].size();
for (int i = 0; i < dim; ++i)
if(adlist[k][i] != father)
{
int x = adlist[k][i];
if(visitedBC[x]) //it's a return edge --> verify if we can reach a higher level
{
if(level_min[k] > level[x])
level_min[k] = level[x];
}
else
{
dfBiconnected(x, k,level, level_min, visitedBC, biconnected, elem);
if(level_min[k] > level_min[x]) // one child has a return edge --> we can reach a higher level
{
level_min[k] = level_min[x];
}
///determine a biconnected component
if(level[k] <= level_min[x]) //the conditon to be able to go back at the articulation point
{
set<int> current;
while(elem.top() != k)
{
current.insert(elem.top());
elem.pop();
}
current.insert(k);
current.insert(x);
biconnected.push_back(current);
}
}
}
}
int main()
{
int i, first, n, m;
vector<int> dg;
/*
fin >> n >> m;
Graph g(n, m);
*/
/*
g.readOriented();
g.bfs(first);
g.printDist();
*/
/*
g.readUndirected();
g.connectedComponents();
*/
///ctc ///time limit exceeded pe un test
/*g.readDirected();
g.stronglyConnectedComponents();
*/
///sortare topologica
/*
g.readDirected();
g.sortTopo();
*/
///HAVEL-HAKIMI
/*
fin >> n;
Graph g(n, 0);
for(int i = 1; i <= n; ++i)
{
fin >> first;
dg.push_back(first);
}
if(g.graphExistsHakimi(dg, n))
fout << "yes";
else fout << "no";
*/
///!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!critical connection
/*
fin >> n;
Graph g(n, 0);
vector<vector<int>>connections = {{0,1},{1,2},{2,0},{1,3}};
vector<vector<int>> sol = g.criticalConnections(n, connections);
for(int i = 0; i <= connections.size(); ++i)
{
for(int j = 0; j <= connections[i].size(); ++j)
fout << connections[i][j] << " ";
fout <<"\n";
}
*/
///componente biconexe
fin >> n >> m;
Graph g(n, m);
g.readUndirected();
g.biconnectedComponents();
return 0;
}
Lupascu Miruna-Stefania MirunaStefania