Anupznk

graph offline 1

Jun 8th, 2021 (edited)
56
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <stdlib.h>
  4. #include <vector>
  5. #include <queue>
  6.  
  7. using namespace std;
  8.  
  9. int bfs(vector<vector<int> > & adj, int pieces [][1], int city, vector<bool> & vis) {
  10.     queue<int> q;
  11.     int foundPieces = 0;
  12.  
  13.     if (!vis[city]){
  14.         q.push(city);
  15.         foundPieces += pieces[city][0];
  16.         vis[city] = true;
  17.     }
  18.  
  19.     while(!q.empty()) {
  20.         int adjCity = q.front();
  21.         q.pop();
  22.  
  23.         for (int i = 0; i < adj[adjCity].size(); i++) {
  24.             int currCity = adj[adjCity][i];
  25.             if (!vis[currCity]) {
  26.                 q.push(currCity);
  27.                 foundPieces += pieces[currCity][0];
  28.                 vis[currCity] = true;
  29.             }
  30.         }
  31.     }
  32.     return foundPieces;
  33. }
  34.  
  35. void dfs(vector<vector<int> > & adj, int pieces [][1], int city, vector<bool> & vis, int & foundPieces) {
  36.  
  37.     if (!vis[city])
  38.         foundPieces += pieces[city][0];
  39.     vis[city] = true;
  40.  
  41.     for (int i = 0; i < adj[city].size(); i++) {
  42.         if (!vis[adj[city][i]]) {
  43.             dfs(adj, pieces, adj[city][i], vis, foundPieces);
  44.         }
  45.     }
  46. }
  47.  
  48. int main() {
  49.  
  50.     int foundPieces = 0, totalPieces = 0;
  51.  
  52.     int numOfCities, numOfRoads, numOfLocations, numOfFriends;
  53.     cin >> numOfCities >> numOfRoads >> numOfLocations >> numOfFriends;
  54.     vector<bool> vis (numOfCities, false);
  55.     vector<vector<int> > adj (numOfCities, vector<int>());
  56.     int friends [numOfFriends][1];
  57.     int friendsCollection[numOfFriends];
  58.  
  59.     int pieces [numOfCities][1];
  60.     for (int i = 0; i<numOfCities; i++) {
  61.         pieces[i][0] = 0;
  62.     }
  63.  
  64.     for (int i = 0; i < numOfRoads; i++) {
  65.         int c1, c2;
  66.         cin >>  c1 >> c2;
  67.         adj[c1].push_back(c2);
  68.         adj[c2].push_back(c1);
  69.     }
  70.  
  71.     for (int i = 0; i < numOfLocations; i++) {
  72.         int c, p;
  73.         cin >> c >> p;
  74.         pieces[c][0] = p;
  75.         totalPieces += p;
  76.     }
  77.  
  78.     for (int i = 0; i < numOfFriends; i++) {
  79.         int c, f;
  80.         cin >> c >> f;
  81.         friends[f][0] = c;
  82.     }
  83.  
  84.     //  USING BFS
  85.  
  86.     ofstream myStream ("result.txt", ios::out);
  87.     if (!myStream.is_open()) {
  88.         cout << "Error accessing the file" << endl;
  89.         exit(1);
  90.     }
  91.  
  92.     myStream << "Finding the result using BFS\n==============================\n";
  93.     cout << "\nWriting BFS results in result.txt file..." << endl;
  94.  
  95.     for (int i = 0; i < numOfFriends; i++) {
  96.         int singleFriendFound = bfs(adj, pieces, friends[i][0], vis);
  97.         friendsCollection[i] = singleFriendFound;
  98.         foundPieces += singleFriendFound;
  99.  
  100.     }
  101.  
  102.     if (foundPieces == totalPieces) {
  103.         myStream << "Mission Accomplished" << endl;
  104.  
  105.     } else {
  106.         myStream << "Mission Impossible" << endl;
  107.  
  108.     }
  109.  
  110.     myStream << foundPieces << " out of " << totalPieces << " pieces are collected" << endl;
  111.  
  112.     for (int i = 0; i < numOfFriends; i++) {
  113.         myStream << i << " collected " << friendsCollection[i] << " pieces" << endl;
  114.     }
  115.  
  116.     //  NOW USING DFS
  117.  
  118.     myStream << "\n\nFinding the result using DFS\n==============================\n";
  119.     cout << "\nWriting DFS results in result.txt file..." << endl;
  120.  
  121.     vector<bool> vis2 (numOfCities, false);
  122.  
  123.     int previouslyFound = 0;
  124.     foundPieces = 0;
  125.  
  126.     for (int i = 0; i < numOfFriends; i++) {
  127.         dfs(adj, pieces, friends[i][0], vis2, foundPieces);
  128.         friendsCollection[i] = foundPieces - previouslyFound;
  129.         previouslyFound = foundPieces;
  130.  
  131.     }
  132.  
  133.     if (foundPieces == totalPieces) {
  134.         myStream << "Mission Accomplished" << endl;
  135.     } else {
  136.         myStream << "Mission Impossible" << endl;
  137.     }
  138.  
  139.     myStream << foundPieces << " out of " << totalPieces << " pieces are collected" << endl;
  140.  
  141.     for (int i = 0; i < numOfFriends; i++) {
  142.         myStream << i << " collected " << friendsCollection[i] << " pieces" << endl;
  143.     }
  144. }
RAW Paste Data