2016 US Open Silver

Debugging Help
#1

Link to problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=644

I need help debugging this code. Sorry, if I am not allowed to ask for debugging help. I have been trying to debug this for the past three days with no results. The program only works for the first, third and fifth testcases.

My logic is to store the graph in terms of adjacency lists. Every time a cow is removed, I remove it from all the adjacency lists. Then I loop through all lists and make sure they do not have length 0. If they do the answer is no.

This is my code:

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;

int main() {
    //freopen("closing.in", "r", stdin);
    //freopen("closing.out", "w", stdout);
    int N,M;
    cin>>N>>M;
    vector<vector<int>> adj_list(N+1);
    for(int i=1;i<=N;i++){
        vector<int> Empty;
        adj_list[i]=Empty;
    }

    int input1,input2;
    for(int i=0;i<M;i++){
        //Fill Adjancey Lists
        cin>>input1>>input2;
        adj_list[input1].push_back(input2);
        adj_list[input2].push_back(input1);
    }

//    for(int i=0;i<N;i++){
//        cout<<i+1<<" ";
//        for(int x=0; x < adj_list[i].size(); x++){
//            cout<<adj_list[i][x]<<" ";
//        }
//        cout<<endl;
//    }

vector<int> Cows;
    for(int i=1;i<=N;i++){
        Cows.push_back(i);
    }

    bool flag1=false;
    for(int i=0;i<Cows.size();i++){
        if(adj_list[Cows[i]].size()==0){
            flag1=true;
            break;
        }
    }
    if(flag1==true){
        cout<<"NO"<<endl;
    }else{
        cout<<"YES"<<endl;
    }

    for(int i=0;i<N-2;i++){

        int eliminate;
        cin>>eliminate;

        for(int x=0;x<adj_list[eliminate].size();x++){
            //Remove the cow that is being eliminated from all adjaceny lists
            adj_list[adj_list[eliminate][x]].erase(remove(adj_list[adj_list[eliminate][x]].begin(), adj_list[adj_list[eliminate][x]].end(), eliminate), adj_list[adj_list[eliminate][x]].end());
        }
        
        Cows.erase(remove(Cows.begin(), Cows.end(), eliminate), Cows.end());
        bool flag=false;

            for (int y = 0; y < Cows.size(); y++) {
                if (adj_list[Cows[y]].size() == 0) {
                    flag = true;

                }
            }

        if(flag==true){
            cout<<"NO"<<endl;
        }else{
            cout<<"YES"<<endl;
        }


    }
    //Last cows is always a yes
    cout<<"YES";
    return 0;
}

Can someone please help me find the mistake?
Thanks

#2

I think your logic is off. Let’s say the graph looked like this:

1 1 2 2 1--2 3 3 4 4 3--4

Your adjacency list would look like this:

adj[1] = [2]
adj[2] = [1]
adj[3] = [4]
adj[4] = [3]

So your code would output that the farm is fully connected because each node has at least one other node connected to it. However, this is not true, as it can be seen that trying to travel from node 1 to node 4 is impossible. I would recommend looking through the DFS module in the guide to learn how to actually implement checking if the farm is fully connected or not. I can’t tell if your “eliminate” function is off because the code is kinda hard to read and I’m lazy. Hope this helps, and let me know if I interpreted your code wrong.

EDIT: Your input is also wrong. You should input N numbers in the last part, but instead you only input N - 2 numbers. Looking deeper into your code, your adjacency list is 2-D, and I am not really sure why that is. You can just declare an adjacency list for this problem as: vector<int> adj_list[N]. I would recommend reading through the DFS module that I provided above, if you have not already, as it provides the information required to solve this problem.