CSES - Aalto Competitive Programming 2024 - wk2 - Homework - Results
Submission details
Task:Connect cities
Sender:Nallue
Submission time:2024-09-05 17:39:27 +0300
Language:C++11
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'std::vector<std::pair<int, int> > BFS(std::vector<bool>&, std::vector<std::vector<int> >&, const int&)':
input/code.cpp:38:38: error: missing template arguments before '(' token
   38 |             addedRoads.push_back(pair(x,ll));
      |                                      ^

Code

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int checkVisited(const vector<bool>& visited){
    for(unsigned int i=0; i< visited.size(); i++){
        if(visited[i]==false) return i;
    }
    return -1;
}

vector<pair<int,int>> BFS(vector<bool>& visited, vector<vector<int>>& roads, const int& init){
    vector<pair<int,int>> addedRoads;

    queue<int> q;
    q.push(init);

    while(not q.empty())
    {
        int x = q.front();
        q.pop();
        for(unsigned int i=0; i<roads[x].size(); i++){
            if(visited[roads[x][i]] == false) q.push(roads[x][i]);
        }
        visited[x] = true;

        if(q.empty()){
            int ll = checkVisited(visited);
            if(ll == -1) return addedRoads;

            roads[ll].push_back(x);
            roads[x].push_back(ll);

            q.push(ll);

            addedRoads.push_back(pair(x,ll));
        }
    }

    return addedRoads;
}

int main(){
    unsigned int n,m;
    cin >> n >> m;

    vector<bool> visited(n, false);
    vector<vector<int>> roads(n);

    for(unsigned int i=0; i<m; i++){
        int a,b;
        cin >> a >> b;
        roads[a-1].push_back(b-1);
        roads[b-1].push_back(a-1);
    }

    
    vector<pair<int,int>> res = BFS(visited, roads, 0);

    cout << res.size() << endl;

    for(unsigned int i=0; i<res.size(); i++){ 
        cout << res[i].first +1 <<" "<< res[i].second+1;
        cout << endl;
    }
}