Pagini recente » Cod sursa (job #1725493) | Cod sursa (job #2229137) | Cod sursa (job #821019) | Cod sursa (job #2769310) | Cod sursa (job #2175393)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX=100000;
struct muchie
{
int x, y;
};
stack <muchie> st;
int T[NMAX+5], niv[NMAX+5], low[NMAX], nivel, sol, n;
vector <int>G[NMAX+5], B[NMAX+5];
void componenta(int x, int y)
{
int i, j;
sol++;
do
{
i=st.top().x;
j=st.top().y;
st.pop();
B[sol].push_back(j);
}while(i!=x and j!=y);
B[sol].push_back(x);
}
void DFS(int nod)
{
int fiu, j;
muchie a;
nivel++;
int it;
niv[nod]=low[nod]=nivel;
for(j=0;j<G[nod].size();j++)
{
it=G[nod][j];
fiu=it;
if(it!=T[nod])
{
if(!niv[fiu])
{
a.x=nod;
a.y=fiu;
st.push(a);
T[fiu]=nod;
DFS(fiu);
if(low[fiu]>=niv[nod])
componenta(nod, fiu);
low[nod]=min(low[nod], low[fiu]);
}
else
low[nod]=min(low[nod], niv[fiu]);
}
}
}
int main()
{
int i, m, xi, yi;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>xi>>yi;
G[xi].push_back(yi);
G[yi].push_back(xi);
}
for(i=1;i<=n;i++)
{
if(!niv[i])
DFS(i);
}
fout<<sol<<"\n";
int j;
for(i=1;i<=sol;i++)
{
for(j=0;j<B[i].size();j++)
fout<<B[i][j]<<" ";
fout<<"\n";
}
return 0;
}