Daca elimini varfurile impare, atunci iei in considerare doar liniile respectiv coloanele care sunt numere neprime. Faci suma tuturor elementelor de pe liniile si coloanele neprime si impartim la 2(o muchie apare de doua ori in graful neordonat)
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int nr_prim(int n){
int i,este_prim=1;
if(n==1){
return 0;
}
for(i=2;i<=sqrt(n);i++){
if(n%i==0){
este_prim=0;
break;
}
}
return este_prim;
}
int main(){
ifstream sgi("subgraf.in");
ofstream sgo("subgraf.out");
int n,i,j,a[101][101],nr_neprime[100],nr=0,s=0,M;
sgi>>n;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
sgi>>a[i][j];
}
if(nr_prim(i)==0){
nr_neprime[nr]=i;
nr++;
}
}
for(i=0;i<nr;i++){
cout<<nr_neprime[i]<<" ";
}
for(i=0;i<nr;i++){
for(j=0;j<nr;j++){
s=s+a[nr_neprime[i]][nr_neprime[j]];
}
}
M=s/2;
sgo<<M;
return 0;
}
