daily pastebin goal
31%
SHARE
TWEET

Untitled

a guest Oct 21st, 2018 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. //I didn't understand what did you mean about ''connected nodes'', so I did everything I could think about.
  3.  
  4. #include <random>
  5. #include <iostream>
  6. #include <vector>
  7. #include <climits>
  8. #include <algorithm>
  9.  
  10. using namespace std;
  11.  
  12. int main() {
  13.     mt19937_64 randomer;
  14.     //graph generation
  15.     size_t vertexCnt = randomer(), edgeCnt = randomer();
  16.     vector<vector<size_t> > graph(vertexCnt);
  17.     for (size_t i = 0; i < edgeCnt; i++) {
  18.         size_t from = randomer() % vertexCnt, to = randomer() % vertexCnt;
  19.         graph[from].push_back(to);
  20.     }
  21.     //counting unique edges
  22.     auto bufferGraph = graph;
  23.     size_t uniqueEdges = 0;
  24.     for (size_t i = 0; i < vertexCnt; i++) {
  25.         sort(bufferGraph[i].begin(), bufferGraph[i].end());
  26.         bufferGraph[i].resize(static_cast<unsigned long>(unique(bufferGraph[i].begin(), bufferGraph[i].end()) -
  27.                                                          bufferGraph[i].begin()));
  28.         uniqueEdges += bufferGraph[i].size();
  29.     }
  30.     //counting connected vertexes
  31.     vector<vector<bool> > matrix(vertexCnt, vector<bool>(vertexCnt));
  32.     size_t connectedPairs = 0;
  33.     for (size_t i = 0; i < vertexCnt; i++)
  34.         for (size_t j = 0; j < bufferGraph[i].size(); j++) {
  35.             matrix[i][bufferGraph[i][j]] = true;
  36.         }
  37.     for (size_t i = 0; i < vertexCnt; i++)
  38.         for (size_t j = i; j < vertexCnt; j++)
  39.             connectedPairs += (matrix[i][j] & matrix[j][i]);
  40.     //counting transitively connected vertexes
  41.     auto transitiveConnectivity = matrix;
  42.     size_t transitivePairs = 0;
  43.     for (size_t temp = 1; temp < vertexCnt; temp *= 2)
  44.         for (size_t i = 0; i < vertexCnt; i++)
  45.             for (size_t j = 0; j < vertexCnt; j++)
  46.                 if (transitiveConnectivity[i][j])
  47.                     for (size_t k = 0; k < vertexCnt; k++)
  48.                         transitiveConnectivity[i][k] = transitiveConnectivity[i][k] | transitiveConnectivity[j][k];
  49.     for (size_t i = 0; i < vertexCnt; i++)
  50.         for (size_t j = i; j < vertexCnt; j++)
  51.             transitivePairs += (transitiveConnectivity[i][j] & transitiveConnectivity[j][i]);
  52.     cout << edgeCnt << ' ' << uniqueEdges << ' ' << connectedPairs << ' ' << transitivePairs;
  53.     return 0;
  54. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top