Question

#419 pbinfo: Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Din acest graf se elimină toate vârfurile care au gradul minim. Să se determine câte muchii va avea subgraful obținut.


Am incercat sa fac problema in mai multe moduri si imi da mereu 20 de puncte, pe exemplu. Ce e gresit la cod (asta e una din variantele mele)?


#include
#include
using namespace std;
ifstream f("subgraf1.in");
ofstream g("subgraf1.out");
int n,a[105][105],c,mn=100000000;
void citire()
{
f>>n;
int x,y;
while(f>>x>>y)
a[x][y]=a[y][x]=1;
}
int grad(int nod)
{
int gr=0,i;
for (i=1;i<=n;i++)
gr+=a[nod][i];
return gr;
}
int main()
{
citire();
for (int i=1;i<=n;i++)
if(mn>grad(i))
mn=grad(i);
for (int i=1;i<=n;i++)
if(grad(i)==mn)
for (int j=1;j<=n;j++)
if(a[i][j]==1)
a[i][j]=0;
for (int i=1;i<=n;i++)
if (grad(i))
c++;
g< return 0;
}

Answer 1

#include<fstream>

using namespace std;

ifstream f("subgraf1.in");

ofstream g("subgraf1.out");

int main()

{

int a[101][101]={0},n,i,j,fr[101],smin,s,k=0;

f>>n;

while(f>>i>>j)

{

a[i] [j]=1;

a[j] [i]=1;

}

smin=n-1;

for(i=1;i<=n;i++)

{

s=0;

for(j=1;j<=n;j++)

if(a[i] [j]==1)

s++;

if(s<smin)

smin=s;

fr[i]=s;

}

for(i=1;i<=n;i++)

{

if(fr[1]==smin)

for(j=1;j<=n;j++)

{

a[i] [j]=0;

a[j] [i]=0;

}

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

if(a[i] [j]==1)

k++;

}

g<<k/2;

return 0;

}

scuze dacă am omis câteva semne de punct și virgula, nu a fost cu intentie=)))