Pagini recente » Cod sursa (job #1509361) | Cod sursa (job #1436526) | Cod sursa (job #1871139) | Cod sursa (job #2870345) | Cod sursa (job #2200491)
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, nrbix, nrc, tmp, d[100001], l[100001];
vector <int> a[100001];
vector <int> bix[100001];
stack <pair<int,int>> st;
void CompBiconexa(int i, int u){
++nrbix;
do{
bix[nrbix].push_back(st.top().x);
st.pop();
}
while(st.top().x!=i && st.top().y!=u);
bix[nrbix].push_back(st.top().x);
}
void Biconex(int u, int tu){
d[u]=l[u]=++tmp;
///parcurg lista de adiacenta a lui u
for(auto i : a[u]){
if(i!=tu && d[i]<d[u]) st.push(make_pair(i,u));
if(d[i]==-1) ///i nevizitat
{
if(u==1) nrc++;
Biconex(i,u);
l[u]=min(l[u],l[i]);
if(l[i]>=d[u]) CompBiconexa(i,u);
}
else if(i!=tu) l[u]=min(l[u],d[i]);
}
}
int main()
{
int i, j;
fin>>n>>m;
while(m--){
fin>>i>>j;
a[i].push_back(j);
a[j].push_back(i);
}
for(i=1; i<=n; i++) d[i]=-1;
st.push(make_pair(1,-1));
Biconex(1,-1);
fout<<nrbix<<'\n';
for(i=1; i<=nrbix; i++)
{
for(auto j : bix[i]) fout<<j<<' ';
fout<<'\n';
}
return 0;
}