Pagini recente » Cod sursa (job #2348203) | Cod sursa (job #1150581) | Cod sursa (job #1117225) | Cod sursa (job #1809400) | Cod sursa (job #1121993)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define NMax 100001
#define inf 210000000
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,nr,nrsol;
vector<int> v[NMax],sol[NMax];
stack<int> st;
int dfn[NMax],low[NMax],viz[NMax],viz2[NMax],Art[NMax];
void afis(int s)
{
++nrsol;
while(s!=st.top())
{
sol[nrsol].push_back(st.top());
st.pop();
}
sol[nrsol].push_back(st.top());
}
void DF(int s)
{
int i,e;
viz2[s]=1;
e=v[s].size();
for(i=0;i<e;i++)
if(viz2[v[s].at(i)]==0) DF(v[s].at(i));
dfn[s]=n-(++nr)+1;
}
void DFS(int s,int ps)
{
int i,e;
low[s]=inf;
viz[s]=1;
st.push(s);
e=v[s].size();
for(i=0;i<e;i++) if(ps!=v[s].at(i))
{
if(viz[v[s].at(i)]==0)
{
DFS(v[s].at(i),s);
if(low[s]>low[v[s].at(i)]) low[s]=low[v[s].at(i)];
if(dfn[s]<=low[v[s].at(i)])
{
Art[s]=1;
afis(s);
}
}
else
{
if(low[s]>dfn[v[s].at(i)]) low[s]=dfn[v[s].at(i)];
}
}
if(low[s]>dfn[s]) low[s]=dfn[s];
}
int main()
{
int i,a,b;
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
if(v[1].size()>1) Art[1]=1;
DF(1);
DFS(1,-1);
g<<nrsol<<"\n";
for(i=1;i<=nrsol;i++)
{
b=sol[i].size();
for(a=b-1;a>=0;a--) g<<sol[i].at(a)<<" ";
g<<"\n";
}
f.close();
g.close();
return 0;
}