Pagini recente » Cod sursa (job #714994) | Cod sursa (job #113012) | Cod sursa (job #404121) | Cod sursa (job #1197446) | Cod sursa (job #2174561)
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
vector<int>g[100001],cc[100001];
int discover[100001],low[100001],nivel,t[100001],sol;
struct muchie
{
int x,y;
};
stack<muchie>st;
void dfs(int nod)
{
nivel++;
discover[nod]=low[nod]=nivel;
for(int i=0;i<g[nod].size();++i)
{
int fiu=g[nod][i];
if(fiu!=t[nod])
{
if(!discover[fiu])
{
muchie c;
c.x=nod;
c.y=fiu;
st.push(c);
t[fiu]=nod;
dfs(fiu);
if(low[fiu]>=discover[nod])
{
int x,y;
sol++;
do
{
x=st.top().x,y=st.top().y;
st.pop();
cc[sol].push_back(y);
}while(x!=nod&&y!=fiu);
cc[sol].push_back(nod);
}
low[nod]=min(low[nod],low[fiu]);
}
low[nod]=min(low[nod],discover[fiu]);
}
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
int n,m,i,x,y;
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
for(i=1;i<=n;++i)
{
if(!discover[i])
dfs(i);
}
printf("%d\n",sol);
for(i=1;i<=sol;++i)
{
for(int j=0;j<cc[i].size();++j)
{
printf("%d ",cc[i][j]);
}
printf("\n");
}
return 0;
}