Pagini recente » Cod sursa (job #545715) | Cod sursa (job #258652) | Cod sursa (job #2439533) | Cod sursa (job #2911425) | Cod sursa (job #2121744)
//30 puncte pe Infoarena - memorie
#include <fstream>
#include<algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct nod
{int inf;
nod *urm;
}*l[100001];
int n, m, nr, k;
int t[100001], niv[100001], low[100001], st[100001][2], v[200001];
bool VIZ[100001];
void adaug(nod *&p,int x)
{
nod *c=new nod;
c->inf=x;
c->urm=p;
p=c;
}
void push (int x, int y)
{
st[++k][0]=x;
st[k][1]=y;
}
void pop (int &x, int &y)
{
x=st[k][0];
y=st[k][1];
k--;
}
void DF(int i)
{nod *c;
VIZ[i]=1;
low[i]=niv[i];
for(c=l[i];c;c=c->urm)
if (!VIZ[c->inf])
{ niv[c->inf] = niv[i]+1;
t[c->inf]=i;
DF(c->inf);
low[i]=min(low[i],low[c->inf]);
if (low[c->inf]>=niv[i]) // i e punct de articulatie, deci din c->inf nu se poate ajunge mai sus de tatal sau
nr++; // numar componenta biconexa
}
else if (c->inf!=t[i])
low[i]=min(low[i],niv[c->inf]);
}
void DF1(int i)
{nod *c;
int x,y,k1,j;
VIZ[i]=1;
low[i]=niv[i];
for(c=l[i];c;c=c->urm)
{
if (c->inf!=t[i] && niv[i]>niv[c->inf])
push (i, c->inf); // adaug muchia de intoarcere in stiva
if (!VIZ[c->inf])
{ niv[c->inf] = niv[i]+1;
t[c->inf]=i;
DF1(c->inf);
low[i]=min(low[i],low[c->inf]);
if (low[c->inf]>=niv[i])
// i e punct de articulatie, deci din c->inf nu se poate ajunge mai sus de tatal sau
{
k1=0;
do // afisez componenta biconexa
{
pop (x,y); // operatia de extragere din stiva se opreste la muchia [x,t[x]]
v[++k1]=x; v[++k1]=y; // g<<x<<" "<<y; muchia din componenta
} while ((x!=i || y!=c->inf) && (x!=c->inf || y!=i));
sort(v+1,v+k1+1);
g<<v[1]<<" ";
for (j=2;j<=k1;j++)
if (v[j]!=v[j-1]) g<<v[j]<<" ";
g<<'\n';
}
}
else if (c->inf!=t[i])
low[i]=min(low[i],niv[c->inf]);
}
}
int main()
{ int x,y,i;
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
adaug(l[y],x);
adaug(l[x],y);
}
niv[1]=1; // daca graful e conex
DF(1);
g<<nr<<'\n';
for (i=1;i<=n;i++)
{
VIZ[i]=0;
niv[i]=0;
low[i]=0;
t[i]=0;
}
niv[1]=1; // daca graful e conex
DF1(1);
g.close();
return 0;
}