竞争编码问题。无向图的 BFS。获取WA

Question

我正在 Hackerrank 上实现图形算法。
Problem statement :
HackerLand 的统治者认为，该国的每个公民都应该有权使用图书馆。不幸的是，HackerLand 遭到龙卷风袭击，摧毁了所有图书馆并阻塞了道路！由于您是 HackerLand 最伟大的程序员，统治者希望您帮助修路并高效地构建一些新库。
HackerLand 有 n 个城市，编号从 1 到 n。这些城市由 m 条双向道路相连。如果满足以下条件，公民可以使用图书馆：

他们所在的城市有一个图书馆。
他们可以通过公路从他们的城市前往拥有图书馆的城市。

下图是HackerLand的样图，虚线表示道路不通：

修任何一条路的费用是c_road美元，在任何一个城市建一座图书馆的费用是c_lib美元。如果在上面的示例中 c_road=2 和 c_lib=3 ，我们将以 5*2 的成本建造 5 条道路，并以 6 的成本建造 2 个图书馆] 。我们不需要重建循环1->2->3->1.
中的其中一条道路您将获得 q 个查询，其中每个查询都包含一个 HackerLand 地图以及 c_lib 和 c_road 的值。对于每个查询，找出使所有公民都能访问图书馆的最低成本，并将其打印在新行上。

我的做法：
我用给定的城市和道路制作了一张图，其中每个城市表示图中的一个节点，每条道路表示一条边。我使用 BFS 算法来查找图的连通分量。然后在每个组件中创建一个库，并构建最少数量的道路以使组件保持连接。

答案：
返回两个中的最小值。

在每个组件中制作图书馆的成本 + 修复道路以使每个组件具有最少数量的道路。
在每个城市建立一个图书馆。
在上面的案例中，修路的成本是 2 美元 (c_road=2)，而建造图书馆的成本是 3 美元 (c_lib=3)。

在这里，该图有两个组成部分：
1,2,3,7（所需道路为3）
5,6,8（所需道路为2）

在每个组件中制作图书馆的成本(2*3=6) + 建设所需道路的成本是(5*2=10) = 16
每个节点建库的成本是(7*3=21)=21
所以，16 就是答案。

我的代码：
注意： 1 本程序中使用的图形索引。

#include<bits/stdc++.h>
using namespace std;

class Graph{
    int v; // number of vertices
    vector<int>*adj;
    public:

        Graph(int V){
            this->v=V+1;
            this->adj=new vector<int>[this->v];
        }

        void addEdge(int u,int v,bool biDir=true){
            adj[u].push_back(v);
            if(biDir)
                adj[v].push_back(u);
        }

        void bfs(int ar[]){
             // create a array of boolean to keep track of visited nodes.
             int numComponent=0,numEdge=0;
            bool visited[this->v];
            for(int i=1;i<this->v;i++)
                visited[i]=false;
            // for each node in graph
            for(int i=1;i<this->v;i++){
                if(!visited[i]){
                    numComponent++;
                    numEdge+=bfsUtill(i,visited);
                }

            }
            ar[0]=numComponent;
            ar[1]=numEdge;
        }

        int bfsUtill(int src, bool visited[]){
            // make a queue and insert src into it
            int numEdge=0;
            queue<int>q;
            q.push(src); // insert src into queue
            // mark first node as visited
            visited[src]=true;
            while(!q.empty()){
                int node=q.front();
                // visit
                cout<<node<<" ";
                // remove this node from queue
                q.pop(); 
                // visit every node adjacent to node 'node' 
                // if that node not visited then visit and enque it.
                for(int adjNode:adj[node]){
                    if(!visited[adjNode]){
                        numEdge++;
                        visited[adjNode]=true;
                        q.push(adjNode);
                    }
                }
            }
            return numEdge;
        }
};

// Complete the roadsAndLibraries function below.

long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) {
// if c_road is greater than c_lib then
if (c_road>c_lib){
    return n*c_lib;
}
Graph g(n);
// make graph of given vertices
for(auto x:cities)
    g.addEdge(x[0],x[1]);

// Array to store number of component and number of edges need to be repaired
int ar[2];
g.bfs(ar); 

long long int  libInEach=n*c_lib;
long long int roadAlso= ar[0]*c_lib+(ar[1]*c_road);

return min(libInEach,roadAlso);
}
// driver code
int main(){
    int t,n,m,c_lib,c_road;
    vector<vector<int>>cities;
    vector<int>temp;
    cin>>t;
    while(t--){
        cin>>n,m,c_lib,c_road;
        int a,b;
        for(int i=0;i<m;i++){
            cin>>a>>b;
            temp.push_back(a,b);
            cities.push_back(temp);
            temp.erase();
        }
        cout<<roadsAndLibraries(n,c_lib,c_road,cities);
    }
    return 0;
}

我得到的一些测试用例的答案是正确的，而一些测试用例的答案是错误的。
我只发布了所需的代码，而不是整个程序。输入被传递到这个函数 roadsAndLibraries() 。
我测试了辅助函数，它们工作正常。

-bfs()
- bfsUtill()
测试用例：

此测试用例的输出：

4
12

Answer 1

我编辑了你的代码。这可能适用于您在 hackerrank 上的测试用例。这在给定的测试用例上运行良好。在任何组件中，如果总顶点数为 n，则可以表示相同连通组件的最小边数为 n-1。

#include<bits/stdc++.h>
using namespace std;

class Graph{
    int v; // number of vertices
    vector<int>*adj;
    public:

        Graph(int V){
            this->v=V+1;
            this->adj=new vector<int>[this->v];
        }

        void addEdge(int u,int v,bool biDir=true){
            adj[u].push_back(v);
            if(biDir)
                adj[v].push_back(u);
        }

        void bfs(int ar[]){
             // create a array of boolean to keep track of visited nodes.
             int numComponent=0,numEdge=0;
            bool visited[this->v];
            for(int i=1;i<this->v;i++)
                visited[i]=false;
            // for each node in graph
            for(int i=1;i<this->v;i++){
                if(!visited[i]){
                    numComponent++;
                    numEdge+=bfsUtill(i,visited);
                }

            }
            ar[0]=numComponent;
            ar[1]=numEdge;
        }

        int bfsUtill(int src, bool visited[]){
            // make a queue and insert src into it
            int numEdge=1;
            queue<int>q;
            q.push(src); // insert src into queue
            // mark first node as visited
            visited[src]=true;
            while(!q.empty()){
                int node=q.front();
                // visit
                cout<<node<<" ";
                // remove this node from queue
                q.pop(); 
                // visit every node adjacent to node 'node' 
                // if that node not visited then visit and enque it.
                for(int adjNode:adj[node]){
                    if(!visited[adjNode]){
                        numEdge++;
                        visited[adjNode]=true;
                        q.push(adjNode);
                    }
                }
            }
            return numEdge-1;
        }
};

// Complete the roadsAndLibraries function below.

long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) {
// if c_road is greater than c_lib then
if (c_road>c_lib){
    return n*c_lib;
}
Graph g(n);
// make graph of given vertices
for(auto x:cities)
    g.addEdge(x[0],x[1]);

// Array to store number of component and number of edges need to be repaired
int ar[2];
g.bfs(ar); 

long long int  libInEach=n*c_lib;
long long int roadAlso= ar[0]*c_lib+(ar[1]*c_road);

return min(libInEach,roadAlso);
}
// driver code
int main(){
    int t,n,m,c_lib,c_road;
    vector<vector<int>>cities;
    vector<int>temp;
    cin>>t;
    while(t--){
        cin>>n,m,c_lib,c_road;
        int a,b;
        for(int i=0;i<m;i++){
            cin>>a>>b;
            temp.push_back(a,b);
            cities.push_back(temp);
            temp.erase();
        }
        cout<<roadsAndLibraries(n,c_lib,c_road,cities);
    }
    return 0;
}

竞争编码问题。无向图的 BFS。获取WA

Problem of competitive coding. BFS of undirected graph. Getting WA

c++

algorithm

graph

breadth-first-search