Probleme bei der Auswertung von Teilgraphen eines Graphen

Question

Hier ist die Frage link.

Gegeben eine ungerichtete Grafik. Dichte eines Graphen ist ^{| E |} ⁄ _{| V |}. Ihre Aufgabe besteht darin, eine nicht-leere Menge von Vertices V zu wählen, so dass der auf V induzierte Subgraph die maximale Dichte hat und diese Dichte druckt. Wenn die maximale Dichte jedoch streng größer als ist, drucken Sie einfach "> 1".

Maximale Anzahl der Ecken: 10
Maximale Anzahl an Kanten: 10

Ich habe gerade eine einfache Lösung, aber in dieser Lösung kann ich den Überblick über das gesamte Graphen halten, Aber wie bekomme ich den Wert der Dichte für kleinere Subgraphen?

#include<iostream> 
#include<vector> 
using namespace std; 
vector<int> adj[1000002];    // adjacency lists adj for storing graph edges 
int node=0;        // initializing for node value(vertices) 
bool visited[100001]={false};   // keeps track of visited nodes(vertices) 
int edge=-1; 
int ans=-1; 
int n;         // keeps optimum value of no. of nodes 
int e;         // keeps optimum value of no. of edges 
void dfs(int s) 
{ 
    node++; 
    edge++; 
    if(edge>0)       
    { 
     float dummy=(float)edge/(float)node; 
     if(dummy>ans) 
      {ans=dummy; 
      e=edge; 
      n=node; 
      } 
    } 
    visited[s]=true; 
    int t; 
    for(int i=0;i!=adj[s].size();i++) 
    { t=adj[s][i]; 
     if(visited[t]==false) 
     { 
      dfs(t); 
     } 
    } 


} 
int main() 
{ 
    long long v,ed,i,j,x,y; 
    cin>>v>>ed; 
    for(long long k=0;k<ed;k++) 
    { 
     cin>>x>>y; 
     adj[x].push_back(y); 
     adj[y].push_back(x); 
    } 
    if(ed>v) 
     cout<<">1"<<endl; 
    else{ 
    for(i=1;i<=v;i++) 
    { 
     if(visited[i]==false) 
     { 
      node=0; 
      edge=-1; 
      dfs(i); 
      //cout<<e<<"/"<<n<<endl; 
     } 
    } 

    cout<<e<<"/"<<n<<endl;} 
} 

Answer 1

Befolgen Sie diese Schritte besseres Ergebnis zu erzielen:

1.Do eine dfs an jeder Komponente die Antwort zu bekommen.

2.Vermeiden Sie die Gleitkommaberechnung, die Sie gerade ausführen, und versuchen Sie die Ganzzahlberechnung.

3.No Grund long long hier mit diesem Bereich verwenden

Ändern Sie den Code, um so etwas wie dies funktionieren sollte:

#include<iostream> 
#include<vector> 
using namespace std; 
vector<int> adj[1000002];    // adjacency lists adj for storing graph edges 
int node=0;        // initializing for node value(vertices) 
bool visited[100001]={false};   // keeps track of visited nodes(vertices) 
int edge=0; 

void dfs(int s) 
{ 
    node++; 
    visited[s]=true; 
    int t; 
    edge+=adj[s].size(); 
    for(int i=0;i!=adj[s].size();i++) 
    { 
     t=adj[s][i]; 
     if(visited[t]==false) 
     { 
      dfs(t); 
     } 

    } 
} 

int main() 
{ 
    int v,ed,i,j,x,y; 
    cin>>v>>ed; 
    for(int k=0;k<ed;k++) 
    { 
     cin>>x>>y; 
     adj[x].push_back(y); 
     adj[y].push_back(x); 
    } 

    int mark[3]; mark[0]=mark[1]=mark[2]=0; 
    int mx_node=0; 
    for(i=1;i<=v;i++) 
    { 
     if(visited[i]==false) 
     { 
      node=0; 
      edge=0; 
      dfs(i); 
      edge/=2; 
      if(node>edge){ 
       mark[0]=1; 
       mx_node=mx_node<node?node:mx_node; 
      } 
      else if(node==edge) mark[1]=1; 
      else mark[2]=1; 
     } 
    } 

    if(mark[2]) printf(">1\n"); 
    else if(mark[1]) printf("1\n"); 
    else printf("%d/%d\n",mx_node-1,mx_node); 
}