Pagini recente » Cod sursa (job #1651384) | Cod sursa (job #2952175) | Cod sursa (job #3223957) | Cod sursa (job #732285) | Cod sursa (job #729021)
Cod sursa(job #729021)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct node
{
int nr;
node *next;
} *v[100005], *fii[100005];
int n,m,nr,st[100005],vf,vfmax,lowlink[100005],depth[100005];
vector < vector <int> > bic;
void add(int a, int b)
{
node *p=new node;
p->nr=b;
p->next=v[a];
v[a]=p;
}
void addf(int a, int b)
{
node *p=new node;
p->nr=b;
p->next=fii[a];
fii[a]=p;
}
void cbic()
{
++nr;
vector <int> comp;
for(int i=vfmax;i>=vf-1;--i) comp.push_back(st[i]);
vfmax=vf-1;
bic.push_back(comp);
}
void afis()
{
int i;
for(i=vf;i;--i) g<<st[i]<<' ';
g<<'\n';
}
int main()
{
int i,j,a,b,vecin,mar;
node *p,*q;
f>>n>>m;
for(i=1;i<=m;++i)
{
f>>a>>b;
add(a,b);
add(b,a);
}
st[1]=1;
vf=vfmax=1;
depth[1]=lowlink[1]=1;
while(vf)
{
i=st[vf];
//g<<vfmax<<' ';
//afis();
p=v[i];
if(p)
{
vecin=p->nr;
if(depth[vecin]) lowlink[i]=min(lowlink[i],depth[vecin]);
else
{
st[++vf]=vecin;
//++vfmax;
vfmax=max(vfmax,vf);
depth[vecin]=lowlink[vecin]=depth[i]+1;
addf(i,vecin);
}
v[i]=v[i]->next;
}
else
{
/*q=fii[i];
while(q)
{
if(lowlink[q->nr]>=depth[i])
{
cbic();
}
lowlink[i]=min(lowlink[i],lowlink[q->nr]);
q=q->next;
}*/
if(lowlink[i]>=depth[st[vf-1]]) cbic();
lowlink[st[vf-1]]=min(lowlink[i], lowlink[st[vf-1]]);
--vf;
}
}
--nr;
//g<<"\n\n";
g<<nr<<'\n';
for(i=0;i<nr;++i)
{
mar=bic[i].size();
for(j=0;j<mar;++j) g<<bic[i][j]<<' ';
g<<'\n';
}
f.close(); g.close();
return 0;
}