Pagini recente » Istoria paginii utilizator/lavib | Cod sursa (job #160744) | Monitorul de evaluare | Diferente pentru utilizator/catalincraciun intre reviziile 10 si 11 | Cod sursa (job #1293064)
#include <cstdio>
#include <vector>
#define Nmax 200005
using namespace std;
int n,niv[Nmax],low[Nmax],nrcomp,st[Nmax],top;
bool viz[Nmax];
vector <int> L[Nmax],Sol[Nmax];
inline void Dfs(int nod, int cnt)
{
niv[nod]=cnt; viz[nod]=true;
vector <int>::iterator it;
for(it=L[nod].begin();it!=L[nod].end();++it)
if(viz[*it])
low[nod]=niv[*it];
else
{
Dfs(*it,cnt+1);
low[nod]=min(low[nod],low[*it]);
}
}
inline void Dfs1(int nod)
{
viz[nod]=true; st[++top]=nod;
vector <int>::iterator it;
for(it=L[nod].begin();it!=L[nod].end();++it)
if(!viz[*it])
{
Dfs1(*it);
if(low[*it]>=niv[nod])
{
++nrcomp;
for(;top && st[top]!=*it;--top) Sol[nrcomp].push_back(st[top]);
Sol[nrcomp].push_back(st[top--]);
Sol[nrcomp].push_back(nod);
}
}
}
int main()
{
int m,x,y,i;
vector <int>::iterator it;
freopen ("biconex.in","r",stdin);
freopen ("biconex.out","w",stdout);
scanf("%d%d", &n,&m);
while(m--)
{
scanf("%d%d", &x,&y);
L[x].push_back(y);
L[y].push_back(x);
}
Dfs(1,0);
for(i=1;i<=n;++i) viz[i]=false;
Dfs1(1);
printf("%d\n", nrcomp);
for(i=1;i<=nrcomp;++i)
{
for(it=Sol[i].begin();it!=Sol[i].end();++it) printf("%d ", *it);
printf("\n");
}
return 0;
}