Pagini recente » Cod sursa (job #951720) | Cod sursa (job #1322442) | Cod sursa (job #2896132) | Cod sursa (job #294635) | Cod sursa (job #654231)
Cod sursa(job #654231)
#include<fstream>
#define inf 32766
using namespace std;
int i,j,x,y,n,st,nivmin[100002],critic[100002],niv[100002],nrfiirad,fiu[3],q,q2,m;
struct nod{short info;nod*adr;}*v[100002],*p;
char viz[100002],viz2[1002];
ofstream g("kgb.out");
void dfs_biconex(int tata,int nd,int nv,int maxx)
{
viz[nd]='1';
nivmin[nd]=nv;
if(tata==1) nrfiirad++;
nod *p=v[nd];
niv[nd]=nv;
while(p)
{
if(!viz[p->info])
{
dfs_biconex(nd,p->info,nv+1,1);
if(nivmin[p->info]>maxx )maxx=nivmin[p->info];
}
else
{
if( nivmin[p->info] < nivmin[nd] ) nivmin[nd]=nivmin[p->info];
p=p->adr;
}
}
if(maxx<niv[nd]) {critic[nd]=1;q++; }
}
void afisare()//verific si nodul 0
{int nr=0,nod,c[1002]={0},ok=1;
for(i=1;i<=n;i++)
if(critic[i]==0){ nr++; c[nr]=i; }
/*if(nr==1) g<<"KGB este forte";
else*/
{
/*g<<"KGB nu este forte\n";
for(i=1;i<=nr;i++) g<<c[i]<<" ";*/
g<<nr+1<<"\n";
}
}
int main()
{
ifstream f("biconex.in");ofstream g("biconex.out");//caz special pt radacina
f>>n>>m;
for(i=1;i<=n;i++)nivmin[i]=inf;
while(f>>x>>y)
{
p=new nod;
p->info=y; p->adr=v[x]; v[x]=p;
p=new nod;
p->info=x; p->adr=v[y]; v[y]=p;
}
for(i=1;i<=n;i++)
if(!viz[i]) dfs_biconex(-1,i,1,1);
critic[1]=1;//critic[x]=1 <=> x nu e critic
if(nrfiirad>1)critic[1]=0;
afisare();
return 0;}