遍历找环

• 先将奶牛排序
• 每一个奶牛只会向右传球或者向左传球（确信）
• 先求出每个奶牛的传球方向
• 然后一共有4种情况（见图），其他情况可以由这4种左右两边延申得出
• 每次遇到环就判断就行
• 

tip：只有第4种情况需要两个球

tip2：n个点n条边一定有环

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

int main(){
    int n, ans = 0; cin >> n;
    vector<int> a(n), edge(n);//向右传：0，向左传：1
    for(int i = 0; i < n; i ++) cin >> a[i];
    sort(a.begin(), a.end());

    edge[n - 1] = 1;//最后一个一定向左传球
    for(int i = 1; i < n - 1; i++)
        if(a[i] - a[i - 1] <= a[i + 1] - a[i]) edge[i] = 1;//i向左传球

    for(int i = 0; i < n; i++)
        if(edge[i] && !edge[i - 1]){//遇到环
            ans++;//一个球
            if(i - 2 >= 0 && !edge[i - 2] && i + 1 < n && edge[i + 1]) ans++;//两个球
        }
    cout << ans;
    return 0;
}

方法2：topo排序（正解）

topo排序可以解决一个牛任意传给另外一个牛（假如传球指定），可解决的范围大一点

• 先找出所有不被传球的奶牛
• 然后从这些奶牛开始dfs（深度搜索）
• 最后找没被传球的奶牛（处于环中）

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int st[N], a[N], edge[N], ind[N];
void dfs(int x){
    st[x] = 1;//来过点x，标记一下
    if(!st[edge[x]]) dfs(edge[x]);
}
int main(){
    int n, ans = 0; cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    sort(a, a + n);

    edge[0] = 1, edge[n - 1] = n - 2;
    for(int i = 1; i < n - 1; i++)
        if(a[i] - a[i - 1] <= a[i + 1] - a[i]) edge[i] = i - 1;//i向右传球
        else edge[i] = i + 1;

    for(int i = 0; i < n; i++) ind[edge[i]]++;//计算入度

    for(int i = 0; i < n; i++) if(!ind[i]) ans++, dfs(i);//topo序遍历

    for(int i = 0; i < n; i++) if(!st[i]) ans++, dfs(i);//去还
    cout << ans;
    return 0;
}