Pagini recente » Cod sursa (job #2683624) | Cod sursa (job #26317) | Cod sursa (job #2283979) | Cod sursa (job #1956670) | Cod sursa (job #1228725)
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
vector <int> l[100010],v[100010];
stack < pair<int,int> > st;
int niv[100010],low[100010];
int x,y,n,m,cb,i,j;
void dfs (int nod, int nivel,int pr) {
niv[nod]=low[nod]=nivel;
pair <int,int> p;
for (int i=0;i<l[nod].size();i++) {
if (l[nod][i]!=pr){
if (!niv[l[nod][i]]) {
st.push(make_pair(nod,l[nod][i]));
dfs(l[nod][i],nivel+1,nod);
low[nod]=min(low[nod],low[l[nod][i]]);
if (niv[nod]<=low[l[nod][i]]) {
cb++;
do {
p = st.top();
st.pop();
v[cb].push_back (p.first);
v[cb].push_back (p.second);
}while (p.first!=nod && p.second!=l[nod][i]);
}
}else
low[nod]=min(low[nod],niv[l[nod][i]]);
}
}
}
int main () {
fin>>n>>m;
while (m--) {
fin>>x>>y;
l[x].push_back(y);
l[y].push_back(x);
}
for (i=1;i<=n;i++)
if (!niv[i])
dfs(i,1,0);
fout<<cb<<"\n";
for (i=1;i<=cb;i++) {
sort (v[i].begin(),v[i].end());
fout<<v[i][0]<<" ";
for (j=1;j<v[i].size();j++) {
if (v[i][j]!=v[i][j-1])
fout<<v[i][j]<<" ";
}
fout<<"\n";
}
return 0;
}