SHARE
TWEET

Untitled

a guest May 19th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<vector>
  5. #include<queue>
  6. #include<deque>
  7. #include<list>
  8. #include<stack>
  9. using namespace std;
  10.  
  11. const int inf = INT_MAX;
  12.  
  13. int n, m;
  14. vector<int> graph[1024];
  15. bool used[1024];
  16.  
  17. // BFS, finding shortest path between two specified vertexes
  18. void BFS(int x, int dest)
  19. {
  20.     used[x] = true;
  21.     queue<int> q;
  22.     q.push(x);
  23.     int fr;
  24.  
  25.     vector<int> parents;
  26.     vector<int> vertexes;
  27.  
  28.     parents.push_back(x);
  29.     vertexes.push_back(x);
  30.  
  31.     bool exited = false;
  32.  
  33.     while (!q.empty())
  34.     {
  35.         fr = q.front();
  36.         q.pop();
  37.         printf("%d ", fr);
  38.  
  39.         for (int i = 0; i < graph[fr].size(); i++)
  40.         {
  41.             if (used[graph[fr][i]] == false)
  42.             {
  43.                 parents.push_back(fr);
  44.                 vertexes.push_back(graph[fr][i]);
  45.  
  46.                 if (graph[fr][i] == dest)
  47.                 {
  48.                     exited = true;
  49.                     break;
  50.                 }
  51.                 q.push(graph[fr][i]);
  52.                 used[graph[fr][i]] = true;
  53.             }
  54.         }
  55.  
  56.         if (exited) break;
  57.     }
  58.  
  59.     list<int> path;
  60.     int i = parents.size() - 1;
  61.     int target = parents[i];
  62.     path.push_front(vertexes[i]);
  63.     i--;
  64.  
  65.     while (i >= 0)
  66.     {
  67.         if (vertexes[i] != target)
  68.         {
  69.             i--;
  70.         }
  71.         else
  72.         {
  73.             path.push_front(target);
  74.             target = parents[i];
  75.             i--;
  76.         }
  77.     }
  78.  
  79.     printf("\n");
  80.  
  81.     for (auto it = path.begin(); it != path.end(); it++)
  82.     {
  83.         printf("%d ", *it);
  84.     }
  85.     printf("\n");
  86. }
  87.  
  88. // graph coloring
  89. // 0 - not visited
  90. // 1 - painted red
  91. // 2 - painted blue
  92. int colors[1000];
  93. void BFSColor(int x)
  94. {
  95.     queue<int> q;
  96.     q.push(x);
  97.     colors[x] = 1;
  98.     int fr;
  99.  
  100.     bool exited = false;
  101.  
  102.     while (!q.empty())
  103.     {
  104.         fr = q.front();
  105.         //printf("%d ", fr);
  106.         q.pop();
  107.  
  108.         int nextColor = (colors[fr] == 1) ? 2 : 1;
  109.  
  110.         for (int i = 0; i < graph[fr].size(); i++)
  111.         {
  112.             if (colors[graph[fr][i]] == 0)
  113.             {
  114.                 colors[graph[fr][i]] = nextColor;
  115.                 q.push(graph[fr][i]);
  116.             }
  117.             else if (colors[graph[fr][i]] == 1)
  118.             {
  119.                 if (colors[fr] == 1)
  120.                 {
  121.                     printf("It is not bipartite!\n");
  122.                     exited = true;
  123.                     break;
  124.                 }
  125.             }
  126.             else if (colors[graph[fr][i]] == 2)
  127.             {
  128.                 if (colors[fr] == 2)
  129.                 {
  130.                     printf("It is not bipartite!\n");
  131.                     exited = true;
  132.                     break;
  133.                 }
  134.             }
  135.         }
  136.         if (exited) break;
  137.     }
  138.     if (!exited) printf("It is bipartite!\n");
  139. }
  140.  
  141. // topological sorting (for DAGs)
  142. stack<int> topologicalSorting;
  143. void DFSTopological(int x)
  144. {
  145.     used[x] = true;
  146.     for (int i = 0; i < graph[x].size(); i++)
  147.     {
  148.         if (used[graph[x][i]] == false)
  149.         {
  150.             DFSTopological(graph[x][i]);
  151.         }
  152.     }
  153.     topologicalSorting.push(x);
  154. }
  155.  
  156. // puskame go za grafi, koito zapochvat ot vruh 1, lesno moje da se modificira i za grafi ot vruh 0
  157. void topologialSort(int x)
  158. {
  159.     for (int i = 0; i < n; i++)
  160.     {
  161.         if (used[i] == false)
  162.         {
  163.             DFSTopological(i);
  164.         }
  165.     }
  166.  
  167.     while (!topologicalSorting.empty())
  168.     {
  169.         printf("%d ", topologicalSorting.top());
  170.         topologicalSorting.pop();
  171.     }
  172. }
  173.  
  174. // modified DFS for SCC algrithm
  175. stack<int> forSCC;
  176. void DFS(int x, bool arrOfUsed[], vector<int> enterGraph[], bool flag)
  177. {
  178.     arrOfUsed[x] = true;
  179.  
  180.     for (int i = 0; i < enterGraph[x].size(); i++)
  181.     {
  182.         if (arrOfUsed[enterGraph[x][i]] == false)
  183.         {
  184.             DFS(enterGraph[x][i], arrOfUsed, enterGraph, flag);
  185.         }
  186.     }
  187.  
  188.     if (flag == true)
  189.     {
  190.         forSCC.push(x);
  191.     }
  192. }
  193.  
  194. vector<int> reversedGraph[1024];
  195. bool usedReversed[1024];
  196.  
  197. int SCC (int x) // works, mind the starting vertex of a graph (0 or 1) !!!
  198. {
  199.     bool flag = true;
  200.     DFS(x, used, graph, flag);
  201.  
  202.     for (int i = 1; i <= n; i++) // from vertex 1
  203.     {
  204.         for (int j = 0; j < graph[i].size(); j++)
  205.         {
  206.             reversedGraph[graph[i][j]].push_back(i);
  207.         }
  208.     }
  209.  
  210.     int counter = 0;
  211.     flag = false;
  212.  
  213.     while (!forSCC.empty())
  214.     {
  215.         if (usedReversed[forSCC.top()] == false)
  216.         {
  217.             DFS(forSCC.top(), usedReversed, reversedGraph, flag);
  218.             counter++;
  219.             forSCC.pop();
  220.         }
  221.         else
  222.         {
  223.             forSCC.pop();
  224.         }
  225.     }
  226.  
  227.     return counter;
  228. }
  229.  
  230. vector<pair<int, int>> graphW[1024];
  231. bool usedW[1024];
  232.  
  233. void zeroOneBFS(int sourceVertex)
  234. {
  235.     vector<int> d(n + 1, inf);
  236.     deque<int> q;
  237.  
  238.     d[sourceVertex] = 0;
  239.     q.push_front(sourceVertex);
  240.     int fr;
  241.  
  242.     while (!q.empty())
  243.     {
  244.         fr = q.front();
  245.         q.pop_front();
  246.  
  247.         for (int i = 0; i < graphW[fr].size(); i++)
  248.         {
  249.             int u = graphW[fr][i].first;
  250.             int w = graphW[fr][i].second;
  251.  
  252.             if (d[fr] + w < d[u])
  253.             {
  254.                 d[u] = d[fr] + w;
  255.                 if (w == 1)
  256.                 {
  257.                     q.push_back(u);
  258.                 }
  259.                 else
  260.                 {
  261.                     q.push_front(u);
  262.                 }
  263.             }
  264.         }
  265.     }
  266.  
  267.     for (int i = 2; i <= n; i++)
  268.     {
  269.         cout << "Shortest distance from " << 1 << " to " << i << " is " << d[i] << '\n';
  270.     }
  271. }
  272.  
  273. struct comp
  274. {
  275.     bool operator() (pair<int, int> p1, pair<int, int> p2)
  276.     {
  277.         return p1.second > p2.second;
  278.     }
  279. };
  280.  
  281. int dist[1024];
  282. // yay, managed to implement it correctly
  283. void dijkstra(int source, bool flag)
  284. {
  285.     priority_queue<pair<int, int>, vector<pair<int, int>>, comp> q;
  286.     q.push({ source, 0 });
  287.  
  288.     pair<int, int> fr;
  289.  
  290.     while (!q.empty())
  291.     {
  292.         fr = q.top();
  293.         q.pop();
  294.  
  295.         int vert = fr.first;
  296.         int w = fr.second;
  297.  
  298.         if (dist[vert] != w)
  299.         {
  300.             continue;
  301.         }
  302.  
  303.         for (int i = 0; i < graph[vert].size(); i++)
  304.         {
  305.             if (dist[graphW[vert][i].first] > dist[vert] + graphW[vert][i].second)
  306.             {
  307.                 dist[graphW[vert][i].first] = dist[vert] + graphW[vert][i].second;
  308.  
  309.                 q.push({ graphW[vert][i].first, dist[graphW[vert][i].first] });
  310.             }
  311.         }
  312.     }
  313. }
  314.  
  315. // Yay,Bellman-Ford works
  316. struct edge
  317. {
  318.     int a, b, cost;
  319. };
  320.  
  321. vector<edge> edges;
  322. int distances[1000];
  323.  
  324. void bellman_ford(int numVertexes, int numEdges)
  325. {
  326.     edge e;
  327.     for (int i = 0; i < numEdges; i++)
  328.     {
  329.         scanf("%d %d %d", &e.a, &e.b, &e.cost);
  330.         edges.push_back(e);
  331.     }
  332.  
  333.     for (int i = 2; i <= numVertexes; i++)
  334.     {
  335.         distances[i] = inf;
  336.     }
  337.  
  338.     distances[1] = 0;
  339.     int counter = 0;
  340.  
  341.     while (true)
  342.     {
  343.         bool change = false;
  344.  
  345.         for (int j = 0; j < numEdges; j++)
  346.         {
  347.             if (distances[edges[j].a] < inf)
  348.             {
  349.                 if (distances[edges[j].b] > distances[edges[j].a] + edges[j].cost)
  350.                 {
  351.                     distances[edges[j].b] = distances[edges[j].a] + edges[j].cost;
  352.                     change = true;
  353.                 }
  354.             }
  355.         }
  356.  
  357.         if (distances[1] < 0)
  358.         {
  359.             cout << "Negative cycle detected!\n";
  360.             return;
  361.         }
  362.  
  363.         counter++;
  364.  
  365.         if (counter == numVertexes && change)
  366.         {
  367.             cout << "Negative cycle detected!\n";
  368.             return;
  369.         }
  370.  
  371.         if (change == false) break;
  372.     }
  373.  
  374.  
  375.     for (int i = 1; i <= numVertexes; i++)
  376.     {
  377.         cout << "Shortes path from vertex 1 to vertex " << i << " is " << distances[i] << '\n';
  378.     }
  379. }
  380.  
  381.  
  382. // Yay, it works
  383. int floydMatrix[1000][1000];
  384.  
  385. void floyd_warshall(int numVertexes, int numEdges)
  386. {
  387.     for (int i = 1; i <= numVertexes; i++)
  388.     {
  389.         for (int j = 1; j <= numVertexes; j++)
  390.         {
  391.             floydMatrix[i][j] = inf;
  392.         }
  393.     }
  394.  
  395.     int from, to, weight;
  396.     for (int i = 0; i < numEdges; i++)
  397.     {
  398.         scanf("%d %d %d", &from, &to, &weight);
  399.         floydMatrix[from][to] = weight;
  400.     }
  401.  
  402.     int i = 1, j = 1;
  403.  
  404.     while (i <= numVertexes && j <= numVertexes)
  405.     {
  406.         floydMatrix[i][j] = 0;
  407.         i++;
  408.         j++;
  409.     }
  410.  
  411.     for (int k = 1; k <= numVertexes; k++)
  412.     {
  413.         for (int i = 1; i <= numVertexes; i++)
  414.         {
  415.             for (int j = 1; j <= numVertexes; j++)
  416.             {
  417.                 if (floydMatrix[i][k] < inf && floydMatrix[k][j] < inf)
  418.                 {
  419.                     floydMatrix[i][j] = min(floydMatrix[i][j], floydMatrix[i][k] + floydMatrix[k][j]);
  420.                     if (i == j && floydMatrix[i][j] < 0)
  421.                     {
  422.                         cout << "Negative cycle detected!\n";
  423.                         return;
  424.                     }
  425.                 }
  426.             }
  427.         }
  428.     }
  429.  
  430.     for (int i = 1; i <= numVertexes; i++)
  431.     {
  432.         cout << "Shortest distance from vertex " << i;
  433.  
  434.         for (int j = 1; j <= numVertexes; j++)
  435.         {
  436.             cout << " to vertex " << j << " is: " << floydMatrix[i][j] << '\n';
  437.         }
  438.  
  439.         cout << '\n';
  440.     }
  441. }
  442.  
  443. struct compInt
  444. {
  445.     bool operator()(pair<int, int> p1, pair<int, int> p2)
  446.     {
  447.         return p1.second > p2.second;
  448.     }
  449. };
  450.  
  451. // moje bi raboti, da go testvam
  452. // trqbva da dobavq i bulev masiv na posetenite vurhove, za da znam koi sa poseteni i da ne zatvorq cikul
  453.  
  454. int n, m;
  455. vector<pair<int, int>>graph[10024];
  456. bool used[10024];
  457.  
  458. struct comp
  459. {
  460.     bool operator()(pair<int, int> p1, pair<int, int> p2)
  461.     {
  462.         return p1.second > p2.second;
  463.     }
  464. };
  465.  
  466. vector<pair<int, int>> rebraMST;
  467.  
  468. int prim(int source)
  469. {
  470.     priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;
  471.     pq.push({ source, 0 });
  472.     pair<int, int> fr;
  473.  
  474.     int MSTWeight = 0;
  475.     int counter = -1;
  476.  
  477.     vector<pair<int, int>> rebraMST;
  478.  
  479.     while (!pq.empty())
  480.     {
  481.         fr.first = pq.top().first;
  482.         fr.second = pq.top().second; pq.pop();
  483.  
  484.         if (used[fr.first]) continue;
  485.         used[fr.first] = true;
  486.  
  487.         MSTWeight += fr.second;
  488.         counter++;
  489.  
  490.         if (counter == n - 1) return MSTWeight;
  491.  
  492.         int minWeightEdge = INT_MAX;
  493.         int secondVert = -1;
  494.  
  495.         for (int i = 0; i < graph[fr.first].size(); i++)
  496.         {
  497.             if (used[graph[fr.first][i].first] == false)
  498.             {
  499.                 pq.push({ graph[fr.first][i].first, graph[fr.first][i].second });
  500.             }
  501.         }
  502.     }
  503.  
  504.     return MSTWeight;
  505. }
  506.  
  507.  
  508. int main()
  509. {  
  510.     scanf("%d %d", &n, &m);
  511.     int x, y, w;
  512.  
  513.     for (int i = 0; i < m; i++)
  514.     {
  515.         scanf("%d %d %d", &x, &y, &w);
  516.         graphW[x].push_back(make_pair(y, w));
  517.         graphW[y].push_back(make_pair(x, w));
  518.     }
  519.  
  520.     //floyd_warshall(n, m);
  521.  
  522.     //BFS(2, 4); // na puviq red dave BFS obhojdane, koeto ne e korektno, zshtoto prekratqvam algorituma predsrochno, za da e korekten namereniq minimalen put
  523.     //BFSColor(1);
  524.     //topologialSort(1);
  525.     //zeroOneBFS(1);
  526.  
  527.     system("pause");
  528.     return 0;
  529. }
  530. */
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