評估圖形子圖的問題

Question

這是link這個問題。

給定無向圖。圖的密度是^{| E |} ⁄ _{| V |}。您的任務是選擇非空集頂點V，使得在V上誘導的子圖具有最大密度並打印此密度。但如果最大密度嚴格大於，只需打印「> 1」。

頂點的最大數量：10
邊數：10

我只是做了一個簡單的解決方案，但在這個解決方案，我可以保持整個圖表的軌道，但是如何獲得較小子圖的密度值？

#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

按照這些步驟，以獲得更好的結果：

1.Do一個DFS每個部件上得到答案。

2.避免您正在執行的浮點計算並嘗試所有整數計算。

3.No理由在這裏使用long long與範圍

修改代碼，這樣的事情應該工作：

#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); 
}