Pagini recente » Cod sursa (job #1954258) | Cod sursa (job #1878166) | Cod sursa (job #821256) | Cod sursa (job #1566405) | Cod sursa (job #1963631)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct nod{int nr;nod *urm;}*a[100001];
int n,m,critic[100001],low[100001],tata[100001],dfn[100001],radacina,nrr,nrcomp,j;
struct el{int u,tu;};
stack<el>S;
int co[100001],vf[200001];
set<int>comp;
set<int>::iterator it;
bool viz[100001];
void adaug(int x,int y)
{
nod *p;
p=new nod;
p->nr=y;
p->urm=a[x];
a[x]=p;
}
void elim(int k,int vecin)
{
el p;
do{
p=S.top();
comp.insert(p.u);
comp.insert(p.tu);
S.pop();
}while(p.u!=k || p.tu!=vecin);
for(it=comp.begin();it!=comp.end();it++)
co[nrcomp]++,vf[++j]=*it;
comp.clear();
}
void df(int k)
{
viz[k] = 1;
low[k]=dfn[k];
nod *p=a[k];
while(p)
{
int vecin=p->nr;
if(!viz[vecin])
{
dfn[vecin]=dfn[k]+1;
tata[vecin]=k;
if(k == radacina)
nrr++;
if(vecin!=tata[k] && !viz[vecin])
S.push({k,vecin});
df(vecin);
if(low[k]>low[vecin])
low[k]=low[vecin];
if(low[vecin] >= dfn[k])
nrcomp++,elim(k,vecin),critic[k]=1;
}
else
if(vecin != tata[k] && low[k] > dfn[vecin])
low[k] = dfn[vecin];
p=p->urm;
}
}
int main()
{
f>>n>>m;
for(int i=1;i<=m;++i)
{
int x,y;
f>>x>>y;
adaug(x,y);
adaug(y,x);
}
for(int i=1;i<=n;i++)
if(!viz[i])
{
S.push({i,-1});
dfn[i]=1;
radacina=i;
nrr=0;
df(i);
if (nrr>1)
critic[radacina]=1;
else
critic[radacina]=0;
}
g<<nrcomp<<'\n';j=1;
for(int i=1;i<=nrcomp;++i)
{
for(int k=1;k<=co[i];++k,++j)
g<<vf[j]<<" ";
g<<'\n';
}
return 0;
}