USACO 5.3 Network of Schools

Compute the minimum number of edges to add to make a directed graph strongly connected. Use Kosaraju’s algorithm to find out strongly connected components and for each SCC count its in degree and out degree and the maximum one is the answer.

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

using namespace std;

int N;
vector<vector<int>> g, rg /* reversed graph */;
vector<int> vs; // post order vertices
vector<bool> visited;
vector<int> cmp; // topological order of strongly connected component.

void add_edge(int from, int to) {
    g[from].push_back(to);
    rg[to].push_back(from);
}

void dfs(int v) {
    visited[v] = true;
    for (int i = 0; i < g[v].size(); ++i) {
        if (visited[g[v][i]]) continue;
        dfs(g[v][i]);
    }
    vs.push_back(v);
}

void rdfs(int v, int k) {
    visited[v] = true;
    cmp[v] = k;
    for (int i = 0; i < rg[v].size(); ++i) {
        if (visited[rg[v][i]]) continue;
        rdfs(rg[v][i], k);
    }
}

int scc() {
    std::fill(visited.begin(), visited.end(), false);
    vs.clear();
    for (int i = 0; i < N; ++i) {
        if (visited[i]) continue;
        dfs(i);
    }
    std::fill(visited.begin(), visited.end(), false);
    int k = 0;
    for (int i = (int)vs.size() - 1; i >= 0; --i) {
        if (visited[vs[i]]) continue;
        rdfs(vs[i], k++);
    }
    return k;
}

int main() {
    ifstream fin("schlnet.in");
    ofstream fout("schlnet.out");
    
    fin >> N;
    g = vector<vector<int>>(N); rg = g;
    vs = vector<int>(N);
    visited = vector<bool>(N, false);
    cmp = vector<int>(N, 0);
    auto ins = vector<int>(N, 0);
    auto outs = vector<int>(N, 0);
    
    for (int i = 0; i < N; ++i) {
        int t; fin >> t;
        while (t) {
            add_edge(i, t - 1);
            fin >> t;
        }
    }
    
    int numOfScc = scc();
    
    //cout << numOfScc << endl;
    
    if(numOfScc == 1)
    {
        cout << 1 << endl << 0 << endl;
        fout << 1 << endl << 0 << endl;

        return 0;
    }
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < g[i].size(); ++j) {
            int v = g[i][j];
            int ii = cmp[i], vv = cmp[v];
            if(ii != vv) {
                ins[vv]++; outs[ii]++;
            }
        }
    }
    
    int ans0 = 0, ans1 = 0;
    for(int i = 0; i < numOfScc; ++i) {
        if(!ins[i])  ++ans0; if(!outs[i]) ++ans1;
    }
    cout << ans0 << endl << max(ans0, ans1) << endl;
    fout << ans0 << endl << max(ans0, ans1) << endl;
    return 0;
}