观察图形规律(CF1829F)

题目传送门

大致思路

根据示例和 $x!=1$ 且 $y!=1$
观察发现,中心顶点的入度唯一当且仅当 $x!=y+1$
这时候直接根据入度计算答案即可
中心顶点入度和除叶子节点入度相等的时,有 $x=y+1$

Code

void solve() {
    int n,m;
    cin >> n >> m;
    vector<vector<int>> a(n+1);
    for (int i = 1; i <= m; i++) {
        int u,v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    int x=1,y=1;
    map<int,int> mp;
    for (int i=1;i<=n;i++) {
        int t=a[i].size();
        mp[t]++;
    }
    vector<pair<int,int>> cnt(mp.begin(),mp.end());
    sort(cnt.begin(),cnt.end());
    //cnt[0]即叶子节点的入度
    if (cnt.size()==3) {
        if (cnt[1].second==1) {
            x=cnt[1].first;
            y=cnt[2].first-1;
        }
        else {
            x=cnt[2].first;
            y=cnt[1].first-1;
        }
    }
    else {
        x=cnt[1].first;
        y=x-1;
    }
    cout << x << ' ' << y << endl;
}