Pagini recente » Cod sursa (job #1482191) | Cod sursa (job #398801) | Istoria paginii runda/wellcodesimulareclasa9-4martie | Cod sursa (job #1607522) | Cod sursa (job #955505)
Cod sursa(job #955505)
#include<fstream>
#include<vector>
#include<stack>
#define pb push_back
#define mp make_pair
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int nr,i,x,y,n,m,xx,yy,j,pr[100100],viz[100100];
vector<int>l[100100];
stack<pair<int,int> >st;
vector<vector<int> >sol;
void dfs(int x,int tata)
{
int nou;
++nr;
viz[x]=nr;
pr[x]=nr;
for(vector<int>::iterator it=l[x].begin();it!=l[x].end();++it)
if(*it!=tata)
{
if(viz[*it])
{
pr[x]=min(pr[x],pr[*it]);
continue;
}
nou=*it;
st.push(mp(x,nou));
dfs(nou,x);
pr[x]=min(pr[nou],pr[x]);
if(pr[nou]>=viz[x])
{
sol.pb(vector<int>());
do{
xx=st.top().first;
yy=st.top().second;
st.pop();
sol.back().pb(yy);
}while(xx!=x&&yy!=nou);
sol.back().pb(x);
}
}
}
int main()
{
f>>n>>m;
for(i=1;i<=m;++i)
{
f>>x>>y;
l[x].pb(y);
l[y].pb(x);
}
for(i=1;i<=n;++i)
if(!viz[i])
dfs(i,0);
g<<sol.size()<<'\n';
for(i=0;i<sol.size();++i)
{
for(j=0;j<sol[i].size();++j)
g<<sol[i][j]<<' ';
g<<'\n';
}
return 0;
}