• 題解

  • $a$和$b$是好*友說明除了這兩個人以外的鄰接集合相同；
  • 做兩次$hash$，分別都處理和$a$相鄰的點排序$hash$，①$a$要算進$a$的相鄰集合，②$a$不算進；
  • 當兩個人不是好*友，一定不會統計，當是且兩個人不相鄰，會僅被②統計，當是且相鄰會僅被①統計；
  • 枚舉所有的$hash$值統計答案；
  • %了$Claris$后學會了對每個點隨機生成一個較大值，異或起來$hash$的方法
  • 這樣用于集合$hash$不用排序，并且刪除一個元素直接異或即可
  • 1 #include<cstdio> 2 #include<map> 3 #include<iostream> 4 #include<vector> 5 #include<algorithm> 6 #define ull unsigned long long 7 using namespace std; 8 const int N=1000010; 9 int n,m; 10 vector<int>s[N]; 11 map<ull,int>mp; 12 map<ull,int>::iterator it; 13 int main(){ 14 freopen("bzoj4264.in","r",stdin); 15 freopen("bzoj4264.out","w",stdout); 16 scanf("%d%d",&n,&m); 17 for(int i=1,x,y;i<=m;i++){ 18 scanf("%d%d",&x,&y); 19 s[x].push_back(y); 20 s[y].push_back(x); 21 } 22 ull ans=0; 23 for(int i=1;i<=n;i++){ 24 sort(s[i].begin(),s[i].end()); 25 unique(s[i].begin(),s[i].end()); 26 ull x=0; 27 for(int j=0;j<(int)s[i].size();j++){ 28 x = x * (ull)1234567891 + s[i][j]; 29 } 30 mp[x]++; 31 } 32 for(it = mp.begin();it!=mp.end();it++){ 33 ans += (ull)it -> second * (it -> second - 1) / 2; 34 } 35 mp.clear(); 36 for(int i=1;i<=n;i++){ 37 s[i].push_back(i); 38 sort(s[i].begin(),s[i].end()); 39 unique(s[i].begin(),s[i].end()); 40 ull x=0; 41 for(int j=0;j<(int)s[i].size();j++){ 42 x = x * (ull)1234567891 + s[i][j]; 43 } 44 mp[x]++; 45 } 46 for(it = mp.begin();it!=mp.end();it++){ 47 ans += (ull)it -> second * (it -> second - 1) / 2; 48 } 49 cout << ans << endl; 50 return 0; 51 } bzoj4264

    ?

?

轉載于:https://www.cnblogs.com/Paul-Guderian/p/10241713.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的【bzoj4264】小C找朋友的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。