题解：AT_abc469_d [ABC469D] The Big Two

· · 题解

题解：AT_abc469_d [ABC469D] The Big Two

题意

给定 m 个决赛选手，求出有多少个数对 x,y， 满足 1 \leq x \lt y \leq N 和每个决赛都至少有一个 x 或者 y。

思路

我们可以分成两种情况来做。

第一种情况，x 和 y 都没有同时出现过，我们可以记录一个数组 a_i 表示 i 在决赛中出现过几次，然后记录一个 map 进行记录 i 在哪场决赛中出现过，最后模拟一下。

第二种情况，x 和 y 同时出现过，直接记录 map 记录同时出现过的局数循环判断即可。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt[200009];
map<pair<int,int>,int> M;
map<int,vector<int>> M2;
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int x,y;
        cin>>x>>y;
        if(x>y)swap(x,y);
        cnt[x]++;cnt[y]++;
        M[{x,y}]++;
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        M2[cnt[i]].push_back(i);
    }
    for(int i=1;i<=n;++i){
        int ne=m-cnt[i];
        if(ne<0||M2.find(ne)==M2.end()){
            continue;
        }
        for(auto j:M2[ne]){
            if(j<=i)continue;
            int x=i,y=j;
            if(M.find({x,y})==M.end()){
                ans++;
            }
        }
    }
    for(auto i:M){ 
        int x=i.first.first;
        int y=i.first.second;
        int s=i.second;
        if(cnt[x]+cnt[y]-s==m)ans++;
    }
    cout<<ans;
    return 0;
}