Pagini recente » Cod sursa (job #1493814) | Cod sursa (job #517058) | Cod sursa (job #1426929) | Cod sursa (job #1493818) | Cod sursa (job #1257162)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int>v[1000];
bool used[10000],c[10000],ok[10000];
int x,y,m,n,niv[10000],l[10000],t[10000],rad,nr,i,stiv[10000][2],a,b,lung,q[10000],u,nrx;
void push(int j,int i)
{stiv[++lung][0]=i;
stiv[lung][1]=j;
}
void pop(int &a,int &b,int &lung)
{
a=stiv[--lung][0];
b=stiv[lung][1];
}
void df(int x)
{vector <int>::iterator it;
used[x]=true;
l[x]=niv[x];
for (it=v[x].begin();it!=v[x].end();it++)
{
if(used[*it]==false)
{niv[*it]=niv[x]+1;
t[*it]=x;
if (x==rad) nr++;
df(*it);
if (l[x] > l[*it]) l[x] = l[*it];
if (l[*it] >= niv[x]) c[x]=true;
}
else if (*it!=t[x]&& l[x]> niv[*it]) l[x] = niv[*it];
}}
void df2(int nod,int &nrx)
{vector <int>::iterator it;
ok[nod]=true;
q[++u]=nod;
for (it=v[x].begin();it!=v[x].end();it++)
{if (c[*it]==1) nrx++;
if (!ok[*it]&&c[*it]!=false) df2(*it,nrx);
}
}
int main()
{f>>n>>m;
for (i=1;i<=m;i++)
{f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for (i=1;i<=n;i++)
if (!used[i])
{niv[i]=1;
rad=i;
nr=0;
df(i);
if (nr > 1) c[rad] = true;
else c[rad] = false;
}
for (i=1;i<=n;i++) ok[i]=false;
for (i=1;i<=n;i++)
if (!ok[i])
{nrx++;
df2(i,nrx);
}
g<<nr;
}