USACO 2022 January Contest Silver Division - Cereal 2

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

First, it's obvious that we want to make a graph out of the cows' preferences and have the cereals as vertexes and the cows as edges. Normally, this leads into having a directed graph and in order to find the answer, we could then find the SCCs.

Problem idea: we want to find the connected components of the graph. Initially the ideas I had were to find the SCCs and solve the problem like that. However, it is enough to consider the graph without the directions and then we have a few cases we need to deal with for each connected component:

• the connected component is a tree, so we can choose a cereal for each cow
• the connected component has a cycle, so we can first solve the problem for the cycle, find the extra edge which links the cycle and then solve the rest of the connected component as if it was a tree.

In the end, the algorithm obtained is linear and will work on every single test case, without needing SCCs.

Source code

The source code in C++ can be seen below.

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

struct edg
{
    int dest, dir, cnt; 
};
vector<vector<edg> > graph;

int hungry, first_cereal, xtr_edge;
bool vis[100002], viscycle[100002], winner[100002];
vector<int> ans;

// here we find the cycle and the edge we need to ignore
void dfscycle(int node, int prev = -1)
{
    viscycle[node] = 1;
    for(int i = 0; i < (int) graph[node].size(); i++)
    {
        if(viscycle[graph[node][i].dest])
        {
            if(first_cereal == -1 && graph[node][i].dest != prev)
            {
                if(graph[node][i].dir == 1)
                    first_cereal = graph[node][i].dest;
                else
                    first_cereal = node;
                xtr_edge = graph[node][i].cnt;
                ans.push_back(graph[node][i].cnt);
                winner[graph[node][i].cnt] = 1;
            }
        }
        else
            dfscycle(graph[node][i].dest, node);
    }
}

// here we solve the problem as if it's a tree
void dfs(int node)
{
    vis[node] = 1;
    for(int i = 0; i < (int) graph[node].size(); i++)
    {
        if(!vis[graph[node][i].dest] && graph[node][i].cnt != xtr_edge)
        {
            winner[graph[node][i].cnt] = 1;
            ans.push_back(graph[node][i].cnt);
            dfs(graph[node][i].dest);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n ,m;
    cin >> n >> m;

    graph.resize(m+1);

    for(int i = 1; i <= n; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back({b, 0, i});
        graph[b].push_back({a, 1, i});
    }

    for(int i = 1; i <= m; i++)
    {
        first_cereal = -1;
        xtr_edge = -1;
        if(!vis[i])
        {
            dfscycle(i);
            if(first_cereal > 0)
                dfs(first_cereal);
            else
                dfs(i);
        }
    }

    for(int i = 1; i <= n; i++)
        if(!winner[i])
            hungry++, ans.push_back(i);

    cout << hungry << '\n';
    for(auto x : ans)
        cout << x << '\n';
    return 0;
}