Pagini recente » Cod sursa (job #1948024) | Cod sursa (job #2990838) | Cod sursa (job #1683967) | Cod sursa (job #3191138) | Cod sursa (job #265549)
Cod sursa(job #265549)
#include<stdio.h>
struct NodStiva {
int x;
int y;
};
struct Nod {
int x;
Nod *next;
};
Nod *a[100001];
int p[100001];
int viz[100001];
NodStiva stack[100001];
int nrBC;
int top;
int nrf;
int n,m,x,y;
int sn[100001];
int biconex[400001];
int art[100001];
int smin[100001];
int min(int a, int b)
{
if (a > b) return b;
return a;
}
int insert(Nod *&u, int val)
{
Nod *q = new Nod;
q -> x = val;
q -> next = u;
u = q;
return 0;
}
int dfs(int s, int niv)
{
sn[s] = niv;
for(Nod *it = a[s]; it != NULL; it = it -> next)
if (!sn[it -> x])
{
p[it -> x] = s;
dfs(it -> x, niv + 1);
}
return 0;
}
int dfmin(int s)
{
viz[s] = 1;
int mini = smin[s];
for(Nod *it = a[s]; it != NULL; it = it -> next)
if ((it -> x) != p[s])
if (mini > sn[it->x]) mini = sn[it->x];
smin[s] = mini;
for(Nod *it = a[s]; it != NULL; it = it -> next)
if (!viz[it -> x])
smin[s] = min(smin[s], dfmin(it -> x));
return smin[s];
}
/******************* Determinarea punctelor de articulatie
int dfArt(int s)
{
viz[s] = 1;
for(Nod *it = a[s]; it != NULL; it = it -> next)
if (!viz[it->x])
{
if (smin[it->x] >= sn[s]) art[s] = 1;
dfArt(it->x);
}
return 0;
}/**///**********************
int df2conex(int s)
{
viz[s] = 1;
for(Nod *it = a[s]; it != NULL; it = it -> next)
if (it -> x != p[s])
{
if (viz[it -> x] && sn[it -> x] <= sn[s])
{
stack[++top].x = s;
stack[top].y = it -> x;
}
if (!viz[it->x])
{
stack[++top].x = s;
stack[top].y = it -> x;
df2conex(it -> x);
if (smin[it -> x] >= sn[s])
{
biconex[++biconex[0]] = -1;
biconex[++biconex[0]] = -1;
nrBC++;
while (stack[top].x != s || stack[top].y != it->x)
{
biconex[++biconex[0]] = stack[top].x;
biconex[++biconex[0]] = stack[top].y;
top--;
}
biconex[++biconex[0]] = stack[top].x;
biconex[++biconex[0]] = stack[top].y;
top--;
}
}
}
return 0;
}
void InitViz()
{
for(int i = 1; i <= n; i++)
viz[i] = 0;
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++)
{
scanf("%d %d", &x, &y);
insert(a[x], y);
insert(a[y], x);
}
// nivelul fiecarui nod
dfs(1,1);
// nivelul minim la care se poate ajunge prin intermediul subarborelui
for(int i = 1; i <= n; i++)
smin[i] = sn[i];
InitViz();
dfmin(1);
/* determina punctele de articulatie
for(int i = 1; i <= n; i++)
viz[i] = 0;
dfArt(1);
for(int i = 1; i <= n; i++)
if (p[i] == 1) nrf++;
art[1] = 0;
if (nrf > 1) art[1] = 1; */
// determina componente biconexe
InitViz();
df2conex(1);
InitViz();
printf("%d\n", nrBC);
for(int i = 3; i <= biconex[0]; i+=2)
{
if (biconex[i] != -1)
{
if (viz[biconex[i]] == 0)
{
printf("%d ",biconex[i]);
viz[biconex[i]] = 1;
}
if (viz[biconex[i+1]] == 0)
{
printf("%d ",biconex[i+1]);
viz[biconex[i+1]] = 1;
}
}
else
{
printf("\n");
InitViz();
}
}
return 0;
}