Pagini recente » Cod sursa (job #2544017) | Cod sursa (job #3269942) | Cod sursa (job #2586794) | Cod sursa (job #2348318) | Cod sursa (job #3226390)
//COMPONENTE BICONEXE ----------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5 + 5;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, depth[nmax], low[nmax], viz[nmax];
vector < int > adj[nmax];
////////////////////////////////////////////////////////////////////////////////
void dfs_depth(int node){
viz[node] = 1;
for(auto elem : adj[node]){
if(viz[elem] == 0){
depth[elem] = depth[node] + 1;
dfs_depth(elem);
}
}
}
void dfs_low(int node, int tata){
low[node] = depth[node];
for(auto elem : adj[node]){
if(elem == tata || depth[elem] > depth[node]) continue;
//muchie verde
low[node] = min(low[node] , depth[elem]);
}
for(auto elem : adj[node]){
if(elem == tata || depth[elem] != depth[node] + 1) continue;
dfs_low(elem , node);
low[node] = min(low[node] , low[elem]);
}
}
stack < int > st;
vector < vector < int > > biconexe;
int cnt_cicluri;
void dfs_biconexe(int node, int tata){
st.push(node);
for(auto u : adj[node]){
if(u == tata || depth[u] != depth[node] + 1) continue;
dfs_biconexe(u , node);
//am gasit o componenta conexa
if(low[u] >= depth[node]){
vector < int > comp_conexa;
while(st.top() != u){
comp_conexa.push_back(st.top());
st.pop();
}
comp_conexa.push_back(u);
comp_conexa.push_back(node);
st.pop();
biconexe.push_back(comp_conexa);
}
}
}
////////////////////////////////////////////////////////////////////////////////
int main()
{
ios_base::sync_with_stdio(0);
fin.tie(0) , fout.tie(0);
fin>>n>>m;
for(int i=1;i<=m;i++){
int x, y;
fin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
//depth --------------------------------------------------------------------
depth[1] = 1;
dfs_depth(1);
//low-----------------------------------------------------------------------
dfs_low(1 , 0);
/*
for(int i=1;i<=n;i++){
cout<<low[i]<<" ";
}
cout<<"\n";
*/
//componente biconexe ------------------------------------------------------
dfs_biconexe(1 , 0);
fout<<biconexe.size()<<"\n";
for(auto elem : biconexe){
for(auto u : elem){
fout<<u<<" ";
}
fout<<"\n";
}
}