「POJ 1236」Network of Schools

#include <cstring>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
/*优化读入
 *@ param l 要读入的int
 */
char ch_buffer;
bool signum;
inline void readInt(int &l) {
    l = 0;
    do
        ch_buffer = getchar();
    while ((ch_buffer < '0' || ch_buffer > '9') && ch_buffer != '0' &&
           ch_buffer != '-');
    if (ch_buffer == '-') ch_buffer = getchar(), signum = true;
    while (ch_buffer <= '9' && ch_buffer >= '0')
        l = (l << 3) + (l << 1) + ch_buffer - '0', ch_buffer = getchar();
    if (signum) l = -l, signum = false;
}
#define M 110             /*题目中可能的最大点数*/
stack<int> st;            /*tarjan算法中的栈*/
int DFN[M];               /*深度优先搜索访问次序*/
int Low[M];               /*能追溯到的最早的次序*/
int ComponentNumber = 0;  /*有向图强连通分量个数*/
int Index = 0;            /*索引号*/
vector<int> Edge[M];      /*邻接表表示*/
vector<int> Component[M]; /*获得强连通分量结果*/
int InComponent[M];       /*记录每个点在第几号强连通分量里*/
int ComponentDegree[M];   /*记录每个强连通分量的度*/
int inDegree[M];          /*入度*/
int outDegree[M];         /*出度*/
/*所给点的数量*/
int n;
/*无向图插入
 *@ param u 第一个顶点编号
 *@ param v 第二个顶点编号
 */
inline void insertMulty(int u, int v) {
    Edge[u].push_back(v), Edge[v].push_back(u);
}
/*有向图插入
 *@ param u 顶点编号
 *@ param v 连通顶点的编号
 */
inline void insert(int u, int v) { Edge[u].push_back(v); }
/*初始化
 *@ param num_of_n 顶点的数量
 */
inline void init(int num_of_n) {
    memset(DFN, 0, sizeof(DFN));
    memset(Low, 0, sizeof(Low));
    memset(inDegree, 0, sizeof(inDegree));
    memset(outDegree, 0, sizeof(outDegree));
    while (!st.empty()) st.pop();
    ComponentNumber = Index = 0;
    n = num_of_n;
}
/*tajan+缩点*/
void tarjan(int u) {
    DFN[u] = Low[u] = ++Index;
    /*入栈*/
    st.push(u);
    int v;
    /*for each (u, v) in E*/
    for (int e = 0; e < Edge[u].size(); e++) {
        v = Edge[u][e];
        if (!DFN[v]) {
            tarjan(v);
            Low[u] = min(Low[u], Low[v]);
            /*!InComponent[v]=>如果不在栈中,*/
            /*这里用这种写法,既可以缩点还能节约一个boolean数组*/
        } else if (!InComponent[v])
            Low[u] = min(Low[u], Low[v]);
    }
    if (DFN[u] == Low[u]) {
        ComponentNumber++;
        do {
            v = st.top(), st.pop();
            /*记录强连通分量*/
            Component[ComponentNumber].push_back(v);
            /*缩点=>degree*/
            InComponent[v] = ComponentNumber;
        } while (v != u); /*until v==u*/
    }
}
/*缩点*/
inline void degree() {
    /*遍历*/
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < Edge[i].size(); j++) {
            int k = Edge[i][j];
            /*这里的InComponent指的是点对应的强连通分量的编号*/
            /*等价于网上许多教程中的belong数组*/
            if (InComponent[i] != InComponent[k]) {
                /*统计入度*/
                inDegree[InComponent[k]]++;
                /*统计出度*/
                outDegree[InComponent[i]]++;
            }
        }
    }
}
int x;
int main(int argc, char const *argv[]) {
    /* code */
    readInt(n);
    init(n);
    for (int i = 0; i < n; i++) {
        /*在c++中,while只根据最后一个","后的变量来判定条件是否成立*/
        while (readInt(x), x) /*所有编号都-1,节约空间*/
            /*如编号为1,存入为0*/
            x--, insert(i, x);
    }
    /*上面编号已减1,故从0开始遍历*/
    for (int i = 0; i < n; i++)
        if (!DFN[i]) tarjan(i);
    /*特殊情况节约时间,避免再往下运行*/
    if (ComponentNumber == 1) cout << "1\n0\n", exit(0);
    /*缩点*/
    degree();
    /*统计入度为0的点*/
    int in_tot = 0, out_tot = 0;
    for (int i = 1; i <= ComponentNumber; i++) {
        if (!inDegree[i]) in_tot++;
        if (!outDegree[i]) out_tot++;
    }
    cout << in_tot << "\n" << max(in_tot, out_tot);
    return 0;
}