USACO 4.3 Street Race

Use DFS to do brutal force search given the small data size. There are two problems:

• Decide the unavoidable points. This can be solved by iterating over each point (except the starting and ending point 0 and N, respectively) and assume the current point is being taken out of the graph. If in such a graph starting from 0 there is still a path to N then the current point being taken out is not an unavoidable point. Otherwise, the current point is an unavoidable point.
• Decide the splitting points. The splitting points must be a subset of unavoidable points. So iterating through all the unavoidable points figured out in first step, and do two search from 0 and the current iterating point respectively, and record the sets of point that two search could reach. If the two sets intersect, then the current point can’t be a splitting point by definition; otherwise the current point is a splitting point.

#include <vector>
#include <iostream>
#include <fstream>
#include <set>
#include <cstring>
#include <algorithm>

using namespace std;

int N;
bool graph[55][55];
bool visited[55];
set<int> st;
int split;

bool dfs(int v, int j) {
    visited[v] = true;
    for (int i = 0; i <= N; ++i) {
        if (visited[i] || !graph[v][i] || i == j || i == v) continue;
        if ((i == N && graph[v][i]) || dfs(i, j)) return true;
    }
    return false;
}

void dfs(int s) {
    st.insert(s);
    for (int i = 0; i <= N; ++i) {
        if (st.count(i) || !graph[s][i] || s == i || i == split) continue;
        dfs(i);
    }
}

int main() {
    ifstream fin("race3.in");
    ofstream fout("race3.out");

    memset(graph, 0, sizeof(graph));
    int n = 0;
    while(!fin.eof()) {
        fin >> n;
        if (n == -2) {
            ++N;
            continue;
        }
        if (n == -1) break;
        graph[N][n] = true;
    }
    --N;

    vector<int> r1, r2;
    for (int i = 1; i <= N - 1; ++i) {
        memset(visited, 0, sizeof(visited));
        if (!dfs(0, i)) r1.push_back(i);
    }

    cout << r1.size(); fout << r1.size();
    for (auto r : r1) {
        st.clear();
        cout << " " << r; fout << " " << r;
        split = r; dfs(0); auto stt = st; st.clear(); dfs(r);
        std::vector<int> common_data;
        set_intersection(st.begin(), st.end(), stt.begin(), stt.end(),
                         std::back_inserter(common_data));
        if (!common_data.empty()) continue;
        r2.push_back(r);
    }
    cout << endl; fout << endl;

    cout << r2.size(); fout << r2.size();
    for (auto r : r2) {
        cout << " " << r; fout << " " << r;
    }
    cout << endl; fout << endl;
}