Pagini recente » Cod sursa (job #2695858) | Cod sursa (job #2165331) | Cod sursa (job #2218177) | Cod sursa (job #2929363) | Cod sursa (job #986149)
Cod sursa(job #986149)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<int> v[100001];
vector<vector<int> > sl;
int dph[100001],low[100001];
stack<int> stx,sty;
void add(int xx,int yy){
vector<int> ax; int x,y;
do{
x=stx.top(); stx.pop();
y=sty.top(); sty.pop();
ax.push_back(x);
ax.push_back(y);
}while(x!=xx||y!=yy);
sl.push_back(ax);
return;
}
void dfs(int nd,int fi,int dh){
dph[nd]=low[nd]=dh;
for(unsigned i=0;i<v[nd].size();i++){
if(v[nd][i]==fi) continue;
if(dph[v[nd][i]]==-1){
stx.push(nd);
sty.push(v[nd][i]);
dfs(v[nd][i],nd,dh+1);
low[nd]=min(low[v[nd][i]],low[nd]);
if(low[v[nd][i]]>=dph[nd])
add(nd,v[nd][i]);
}else low[nd]=min(low[nd],dph[v[nd][i]]);
}
return;
}
int main()
{
int n,m;
f>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=0;i<=n;i++)
dph[i]=-1;
dfs(1,0,0);
g<<sl.size()<<'\n';
for(unsigned i=0;i<sl.size();i++,g<<'\n'){
sort(sl[i].begin(),sl[i].end());
sl[i].erase(unique(sl[i].begin(),sl[i].end()),sl[i].end());
for(unsigned j=0;j<sl[i].size();j++)
g<<sl[i][j]<<" ";
}
return 0;
}