NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2017高中組決賽
 D. 最大不團問題

作者 主題: D. 最大不團問題  (閱讀 250 次)

oToToT

  • 新手
  • *
  • 文章數: 5
    • 檢視個人資料
D. 最大不團問題
« 於: 三月 19, 2018, 02:32:42 pm »

看是不是一個團就好
代碼: [選擇]
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int N = 100000 + 5;

set<int> G[N];

int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m; cin>>n>>m;
for(int i=0;i<m;i++){
int u, v; cin>>u>>v;
if(u==v) continue;
G[u].insert(v);
G[v].insert(u);
}
bool flag = false;
for(int i=1;i<=n;i++){
if(G[i].size() < n-1) flag = true;
}
cout<<(flag?n:0)<<'\n';
return 0;
}
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
Re: D. 最大不團問題
« 回覆 #1 於: 十月 08, 2018, 04:24:59 pm »

其實只要檢查 m!=n*(n-1)*2 即可,後面的資料完全不需要輸入。
另外,因為 n 最大為 10^5,
n*(n-1) 會超過 int 的範圍,要注意,
而因為 m 最大也是 10^5,
所以可以 反推回去 n 超過 500 的情況一定是 n,
就不用再乘了。
也就是:
代碼: [選擇]
if (n>=500||m!=n*(n-1)*2) cout << n << endl;
else cout << 0 << endl;
« 上次編輯: 十月 09, 2018, 02:42:02 pm 由 sagit »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2017高中組決賽
 D. 最大不團問題