Advertisement
Guest User

Untitled

a guest
Dec 13th, 2019
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.17 KB | None | 0 0
  1. //
  2. //
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7.  
  8. int main()  {
  9.     cin.sync_with_stdio(0);
  10.     cin.tie(0);
  11.     cout.tie(0);
  12.     int n, m; cin >> n >> m;
  13.     ll cnt=0;
  14.     vector<int> v[n+1];
  15.     for (int i=1; i<=m; i++)
  16.     {
  17.         int a, b; cin >> a >> b;
  18.         v[a].push_back(b);
  19.         v[b].push_back(a);
  20.     }
  21.     bool visited[n+1]; for (int i=1; i<=n; i++) visited[i]=false;
  22.    
  23.     for (int i=1; i<=n; i++) sort(v[i].begin(),v[i].end());
  24.    
  25.     queue<int> q; q.push(1);
  26.     while (!q.empty())
  27.     {
  28.         int a=q.front(); q.pop();
  29.         if (visited[a]) continue;
  30.         unordered_map<int,bool> done;
  31.         for (int i=0; i<v[a].size(); i++)
  32.         {
  33.             int b=v[a][i];
  34.             if (visited[b]) continue;
  35.             for (int j=0; j<v[b].size(); j++)
  36.             {
  37.                 int c=v[b][j];
  38.                 if (visited[c]||done[c]) continue;
  39.                 vector<int>::iterator low=lower_bound(v[a].begin(),v[a].end(),c);
  40.                 if (low!=v[a].end()&&*low==c)
  41.                 {
  42.                 //  cout << a << " " << b << " " << c << endl;
  43.                     cnt++;
  44.                 }
  45.             //  for (int k=0; k<v[c].size(); k++) if (v[c][k]==a) cnt++;
  46.             }
  47.             done[b]=true;
  48.         }
  49.         visited[a]=true;
  50.         for (int i=0; i<v[a].size(); i++)
  51.         {
  52.             int b=v[a][i];
  53.             q.push(b);
  54.         }
  55.     }
  56.     cout << cnt << endl;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement