Pagini recente » Cod sursa (job #1442829) | Cod sursa (job #252240) | Cod sursa (job #1745951) | Cod sursa (job #2100246) | Cod sursa (job #930552)
Cod sursa(job #930552)
#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define max 100005
#define Min(a,b) ((a)<(b) ? (a):(b))
vector<int> roads[max],dfn,low;
int n,m;
vector< vector<int> > final;
stack< pair<int,int> > stk;
void shit(int a,int b)
{
vector<int> res; int x,y;
do
{
x=stk.top().first;y=stk.top().second;
stk.pop();
res.push_back(x); res.push_back(y);
}while(x!=a || b!=y);
final.push_back(res);
}
void DFS(int n,int fn,int number)
{
low[n]=number;
dfn[n]=number;
for(vector<int>::iterator it=roads[n].begin(); it!=roads[n].end();it++)
{
if(*it==fn) continue;
if(dfn[*it]==-1)
{
stk.push( make_pair(n,*it) );
DFS(*it,n,number+1);
low[n]=Min(low[n],low[*it]);
if( low[*it] >= dfn[n] )
shit(n,*it);
}
else
low[n]=Min(low[n],low[*it]);
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for(;m>0;m--)
{
int x,y;
scanf("%d%d",&x,&y);
roads[x].push_back(y);
roads[y].push_back(x);
}
dfn.resize(n+1),
dfn.assign(n+1,-1);
low.resize(n+1);
DFS(1,0,0);
printf("%d\n",final.size());
for(size_t i=0;i<final.size();i++)
{
sort(final[i].begin(),final[i].end());
final[i].erase(unique(final[i].begin(),final[i].end()),final[i].end());
for(size_t j=0;j<final[i].size();j++)
printf("%d ",final[i][j]);
printf("\n");
}
}