Pagini recente » Cod sursa (job #805211) | Cod sursa (job #106953) | Cod sursa (job #1804580) | Cod sursa (job #3130688) | Cod sursa (job #703334)
Cod sursa(job #703334)
#include<stdio.h>
#include<stdlib.h>
typedef struct nod{ int x; nod *urm;}NODE;
NODE *v[100010];
int n,m,d[100010],min[100010],k;
int minim(int a, int b)
{
if(a<=b) return a;
return b;
}
void citire()
{
FILE *f=fopen("biconex.in","r");
NODE*q;
int x,y;
fscanf(f,"%d%d",&n,&m);
for(int i=0;i<m;++i)
{
fscanf(f,"%d%d",&x,&y);
q=(NODE*)malloc(sizeof(NODE));
q->x=y;
q->urm = v[x];
v[x] = q;
q=(NODE*)malloc(sizeof(NODE));
q->x=x;
q->urm = v[y];
v[y] = q;
}
fclose(f);
}
void dfs(int nod,int tata,int dist)
{
d[nod]=min[nod]=dist;
int nrf=0;
bool critic = false;
NODE *q=v[nod];
while(q)
{
if(q->x != tata)
if(d[q->x]==-1)
{
++nrf;
dfs(q->x,nod,dist+1);
min[nod] = minim(min[q->x],min[nod]);
if(min[q->x] >= d[nod]) critic = true;
}
else
min[nod] = minim(min[nod],d[q->x]);
q=q->urm;
}
if( (nod == 1 && nrf > 1) || (nod!=1 && critic) )
//printf("%d ",nod);
++k;
}
int main()
{
citire();
for(int i=1;i<=n;++i) d[i]=-1;
dfs(1,0,0);
FILE *f=fopen("biconex.out","w");
fprintf(f,"%d\n",k+1);
fclose(f);
return 0;
}