Pagini recente » Cod sursa (job #703862) | Cod sursa (job #2656561) | Cod sursa (job #2752107) | Cod sursa (job #1498605) | Cod sursa (job #2348407)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#include <stdio.h>
#include <stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int nma[100001], nivel[100001],n, tata,Viz[100001],radacina,m,nrc;
vector <int> L[100001],C[100001];
stack <int> S;
void Citire()
{int i, x, y;
f>>n>>m;
for(i=1;i<=m;i++)
{ f>>x>>y;
L[x].push_back(y);
L[y].push_back(x);
}
}
/*void dfs(int k)
{ int j;
Viz[k]=1;
for(j=0;j<L[k].size();j++)
if(Viz[L[k][j]]==0)
{ tata[L[k][j]]=k;
dfs(L[k][j]);}
}
*/
void pct(int k, int x)
{
if(nivel[k]<=nma[x]&&k!=radacina)
cout<<k<<" ";
}
void punte(int k,int x)
{
if(nivel[k]< nma[x])
cout<<k<<" "<<x<<endl;
}
void comp(int k,int x)
{int nr;
if(nivel[k]<=nma[x])
{while(S.top()!=x)
{ nr=S.top();
C[nrc].push_back(nr);
S.pop();
}
C[nrc].push_back(x);
S.pop();
C[nrc].push_back(k);}
}
void dfs2(int k,int tata)
{ Viz[k]=1;
S.push(k);
nivel[k]=nivel[tata]+1;
nma[k]=nivel[k];
int j,x;
for(j=0;j<L[k].size();j++)
{ x=L[k][j];
if(x!=tata)
{ if(Viz[x]==1)
{ if(nma[k]>nivel[x])
nma[k]=nivel[x];
}
else { dfs2(x,k);
if(nma[k]>nma[x])
nma[k]=nma[x];
// pct(k,x);
// punte(k,x);
nrc++;
comp(k,x);
}
}
}
}
void afisare()
{ int i ,j,nr=0 ;
for(i=1;i<=nrc;i++)
if(!C[i].empty())
nr++;
g<<nr<<endl;
for(i=1;i<=nrc;i++)
{for(j=0;j<C[i].size();j++)
g<<C[i][j]<<" ";
if(C[i].size()!=0)
g<<endl;}
}
int main()
{
Citire();
radacina=1;
//nivel[radacina]=1;
//nma[radacina]=1;
//dfs(radacina);
memset(Viz, 0, sizeof(Viz));
dfs2(radacina,1);
afisare();
f.close();
g.close();
return 0;
}