Advertisement
DASBD72

252

May 26th, 2019
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <cstring>
  7. #include <utility>
  8. using namespace std;
  9. int main(){
  10. int N, M, x, y, ans = 0;
  11. cin >> N >> M;
  12. vector<int> connect[N];
  13. bool adj[N][N]={};
  14. for(int i = 0;i < M;i++){
  15. cin >> x >> y;
  16. connect[x].push_back(y);
  17. connect[y].push_back(x);
  18. adj[x][y]=true;
  19. adj[y][x]=true;
  20. }
  21. for(int p1 = 0;p1 < N;p1++){
  22.  
  23. if(connect[p1].size() > sqrt(M)){
  24. for(int p2,i2 = 0;i2 < connect[p1].size();i2++){
  25. p2 = connect[p1][i2];
  26. for(int p3,i3 = 0;i3 < connect[p2].size();i3++){
  27. p3 = connect[p2][i3];
  28. for(int ph,i4 = 0;i4 < connect[p3].size();i4++){
  29. ph = connect[p3][i4];
  30. if(ph==p1){
  31. ans++;
  32. //printf("%d %d %d\n",p1,p2,p3);
  33. }
  34. }
  35. }
  36. }
  37. }
  38. else{
  39. for(int i = 0 ;i < N;i++)if(adj[p1][i] == true)
  40. for(int j = i+1;j < N;j++)if(adj[p1][j] == true){
  41. if(adj[i][j]==true){
  42. ans+=2;
  43. //printf("%d %d %d\n",p1,i,j);
  44. }
  45. }
  46. }
  47. }
  48. cout << ans/6 << endl;
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement