题解：P14503 [NCPC 2025] Instagraph

· · 题解

思路

考虑处理每个人的入度。

当 a 关注 b 时，b 的入度要增加 1。

当之后 b 关注 a 后，即两人互关时，为了让 a 出度为 0，要把 b 的贡献从 a 中删除，即将 a 的入度减少 1。

代码

#include<bits/stdc++.h>
#define endl "\n"
#define int long long
#define f(n) for(int i=1;i<=n;i++)
#define IOS cin.tie(0),cout.tie(0),ios::sync_with_stdio(0)
using namespace std;
int n,m,x,y,r[200005],maxn=-1,maxi;
map<int,map<int,int>>e;//常数巨大让我拿下当前最劣解 
signed main(){
    IOS;cin>>n>>m;
    f(m){
        cin>>x>>y;
        if(e[y][x])r[x]--;//y之前关注过x，现在两人互关，去除y对x的贡献 
        else r[y]++;//x对y贡献一个关注 
        e[x][y]=1;//记录x关注过y 
    }
    f(n)if(r[i]>maxn)maxn=r[i],maxi=i;//找出最大名人中心性
    cout<<maxi<<" "<<maxn;
    return 0;
}