图中的基环树

蹄球 https://www.acwing.com/problem/content/description/1740/

判断 只有两种情况

分析知道
对非基环树 只能形成有两个点的环 1/2
对基环树 转化为找入度为0的点
p[i ] 表示第i个点的出度 d[i]表示这个点的入度

#include 
#include 
#include 

using namespace std;

const int N = 110, INF = 1e8;

int n;
int q[N], p[N], d[N];//p出度 d入度

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> q[i];
    q[0] = -INF, q[n + 1] = INF;
    sort(q + 1, q + n + 1);

    for (int i = 1; i <= n; i ++ )//建立图 使用d[]记录入度 p记录出度
        if (q[i] - q[i - 1] <= q[i + 1] - q[i])
        {
            p[i] = i - 1;
            d[i - 1] ++ ;
        }
        else
        {
            p[i] = i + 1;
            d[i + 1] ++ ;//i+1的出度增加
        }

    int res = 0;
    for (int i = 1; i <= n; i ++ )//遍历每个点
        if (!d[i]) res += 2;//如果这个点的入度为0那就是他了
        else if (p[p[i]] == i && d[i] == 1 && d[p[i]] == 1)//如果i走两边回到自身 并且这个环的两个点的入度为1（为对方）
            res ++ ;//说明找到了环
        //其他情况不增加
    cout << res / 2 << endl;//1/2是精度 所以前面计算的时候+两倍不用担心精度问题
    return 0;
}