Pagini recente » Cod sursa (job #87533) | Cod sursa (job #170534) | Cod sursa (job #829075) | Cod sursa (job #3245068) | Cod sursa (job #843271)
Cod sursa(job #843271)
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int urca[100001],nivel[100001];
vector <int> lv[100005];
vector <int> com[100005];
int nr;
vector <int> stack;
int cate,start;
void dfs(int nod,int niv)
{ int i;
urca[nod]=niv;
nivel[nod]=niv;
stack.push_back(nod);
for(i=0;i<lv[nod].size();i++)
{
if(!nivel[lv[nod][i]])
{
dfs(lv[nod][i],niv+1);
if(urca[nod]>urca[lv[nod][i]])urca[nod]=urca[lv[nod][i]];
else
if(urca[lv[nod][i]]>=niv)
{
int u;
u=stack.size()-1;
nr++;
while(stack[u]!=nod)
{
com[nr].push_back(stack[u--]);
stack.pop_back();
}
com[nr].push_back(stack[u]);
}
}
else
if(nivel[lv[nod][i]]&&nivel[lv[nod][i]]<niv-1) urca[nod]=nivel[lv[nod][i]];
}
}
int n,m;
int main()
{
int i;
fin>>n;
fin>>m;
for(i=1;i<=m;i++)
{
int x,y;
fin>>x>>y;
lv[x].push_back(y);
lv[y].push_back(x);
}
dfs(1,1);
fout<<nr<<"\n";
for(i=1;i<=nr;i++)
{
int j,k;
k=com[i].size();
for(j=0;j<k;j++)
fout<<com[i][j]<<" ";
fout<<"\n";
}
}