• API
• FAQ
• Tools
• Archive
daily pastebin goal
16%
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.

Top