USACO 2019 US Open Contest Bronze Division - Milk Factory

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Either brute force or DFS works for this problem, due to the graph structure given.

Source codes

The source codes in C++ and Python can be seen below.

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

int cnt = 0;
vector<vector<int> > graph;
bool viz[102];
void dfs(int x)
{
    cnt++;
    viz[x] = 1;
    for(auto nxt : graph[x])
        if(!viz[nxt])
            dfs(nxt);
}
int main() 
{
    ifstream cin("factory.in");
    ofstream cout("factory.out");

    int n;
    cin >> n;

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

    for(int i = 1; i <= n; i++)
    {
        cnt = 0;
        dfs(i);
        if(cnt == n)
        {
            cout << i;
            return 0;
        }
        for(int j = 1; j <= n; j++)
            viz[j] = 0;
    }
    cout << -1;
    return 0;
}

def dfs(x):
    global cnt
    cnt += 1
    viz[x] = True
    for nxt in graph[x]:
        if not viz[nxt]:
            dfs(nxt)

with open("factory.in", "r") as fin:
    n = int(fin.readline().strip())
    graph = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        a, b = map(int, fin.readline().split())
        graph[b].append(a)

viz = [False] * (n + 1)
ans = -1
for i in range(1, n + 1):
    cnt = 0
    dfs(i)
    if cnt == n:
        ans = i
        break
    viz = [False] * (n + 1)

with open("factory.out", "w") as fout:
    fout.write(str(ans))