Pagini recente » Cod sursa (job #3189784) | Cod sursa (job #2270599) | Cod sursa (job #1617012) | Cod sursa (job #1889967) | Cod sursa (job #2202058)
#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, 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;
int xx, yy;
bitset <100005> ap;
do{
xx=st.top().x;
yy=st.top().y;
if(ap[xx]==0) ap[xx]=1, bix[nrbix].push_back(xx);
if(ap[yy]==0) ap[yy]=1, bix[nrbix].push_back(yy);
st.pop();
}
while(xx!=i || yy!=u);
}
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
{
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++)
{
sort(bix[i].begin(),bix[i].end());
for(auto j : bix[i]) fout<<j<<' ';
fout<<'\n';
}
return 0;
}