Pagini recente » Cod sursa (job #1979530) | Cod sursa (job #196095) | Cod sursa (job #1947577) | Cod sursa (job #1391397) | Cod sursa (job #993803)
Cod sursa(job #993803)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <bitset>
FILE *f=fopen("biconex.in","r");
FILE *g=fopen("biconex.out","w");
#define pb push_back
using namespace std;
const int Nmax = 100005;
const int Mmax = 200005;
bitset< Nmax > used,artic;
vector< int > lv[Nmax];
int tata[Nmax],niv[Nmax],nmin[Nmax];
int N,M,fr;
void DFS(int nodc)
{
used[ nodc ] = true;
nmin [ nodc ] = niv [ nodc ];
for(vector< int > ::iterator it = lv[nodc].begin();it!=lv[nodc].end();++it)
if(used[ *it ] == false)
{
niv [ *it ] = niv [ nodc ] + 1;
tata [ *it ] = nodc;
if( nodc == 1) ++fr;
DFS( *it );
if( nmin[ * it ] < nmin[ nodc ]) nmin[ nodc ] = nmin[ *it ];
if( nmin[ *it ] >= niv[ nodc ]) artic[ nodc ] = 1;
}
else if( tata[ nodc ] != *it && niv[*it] < nmin[nodc])nmin[nodc]=niv[*it];
}
void get_Graph()
{
fscanf(f,"%d%d",&N,&M);
int a,b;
for(int i=1;i<=M;++i)
{
fscanf(f,"%d%d",&a,&b);
lv[a].pb(b);
lv[b].pb(a);
}
}
int main()
{
get_Graph();
DFS(1);
int total=0;
if(fr<=1)artic[1]=0;
for(int i=1;i<=N;++i)
if(artic[i]==true)++total;
fprintf(g,"%d\n",total+1);
return 0;
}