评估图形子图的问题

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