SHARE
TWEET

Untitled

a guest Dec 8th, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. vector<int> bfs(vector<int> someGraph[], int source, int destination) {    
  9.     int prev[1000] = {0};                                                  
  10.     bool visited[1000] = {false};                                          
  11.     prev[source] = 0;                                                      )
  12.     queue<int> q;
  13.     q.push(source);
  14.     while (!q.empty()) {
  15.         int cur = q.front();
  16.         q.pop();
  17.         for (int j = 0; j < someGraph[cur].size(); j++) {
  18.             if (!visited[someGraph[cur][j]]) {
  19.                 visited[someGraph[cur][j]] = true;
  20.                 prev[someGraph[cur][j]] = cur;
  21.                 q.push(someGraph[cur][j]);
  22.             }
  23.         }
  24.     }
  25.     vector<int> path;                                                      
  26.     for (int i = destination; i != source; i = prev[i]) {                  
  27.         path.push_back(i);
  28.     }
  29.     path.push_back(source);
  30.  
  31.     return path;
  32. }
  33.  
  34. void printPath(vector<int> path) {                                          
  35.     for (int i = path.size() - 1; i >=0; i--) {
  36.         cout << path[i] << " ";
  37.     }
  38.     cout << "\n";
  39. }
  40.  
  41. int main() {
  42.     ifstream fin("graphedges14.txt");
  43.     int n1, n2;
  44.     int edges = 0;
  45.     vector<int> graph[1000];                            
  46.  
  47.     while (fin >> n1) {                                
  48.         fin >> n2;                                    
  49.         graph[n1].push_back(n2);                        
  50.         graph[n2].push_back(n1);                        
  51.         edges++;
  52.     }
  53.     cout << edges << "\n";
  54.  
  55.     int isolates[1000];
  56.     int numOfIsolates = 0;
  57.     int max = 0;
  58.     int maxNode;
  59.  
  60.     for (int i = 0; i < 1000; i++) {                    
  61.         if (graph[i].empty()) {                        
  62.             isolates[numOfIsolates++] = i;              
  63.         }
  64.     }
  65.  
  66.     cout << numOfIsolates << "\n";
  67.  
  68.     for (int i = 0; i < numOfIsolates; i++) {
  69.         cout << isolates[i] << " ";
  70.     }
  71.  
  72.     for (int i = 0; i < 1000; i++) {                  
  73.         if (graph[i].size() > max) {                  
  74.             maxNode = i;                              
  75.             max = graph[i].size();
  76.         }
  77.     }
  78.     cout << "\n";
  79.     cout << maxNode << " " << max << "\n";
  80.  
  81.     vector<int> maxDist;                                
  82.  
  83.     for (int i = 0; i < 1000; i++) {
  84.         for (int j = 0; j < 1000; j++) {
  85.             if(!graph[i].empty() && !graph[j].empty()) {
  86.                 vector<int> dist = bfs(graph, i, j);    
  87.                 if (dist > maxDist) {
  88.                     maxDist = dist;
  89.                 }
  90.             }
  91.         }
  92.     }
  93.  
  94.     printPath(maxDist);
  95.  
  96.     int a = 363; int b = 642;
  97.     int c = 738; int d = 685;
  98.     int e = 739; int f = 891;
  99.     vector<int> path = bfs(graph, a, b);
  100.     printPath(path);
  101.     path.clear();
  102.     path = bfs(graph, c, d);
  103.     printPath(path);
  104.     path.clear();
  105.     path = bfs(graph, e, f);
  106.     printPath(path);
  107.  
  108.     vector<int> newGraph[1000];
  109.     fin.clear();
  110.     fin.seekg(0);
  111.     edges = 0;
  112.     while (fin >> n1) {
  113.         if (n1 % 17 == 0 || n1 == 224 || n1 == 611 || n1 == 424 || n1 == 982 || n1 == 61) {
  114.             fin >> n2;
  115.             continue;
  116.         }
  117.         fin >> n2;
  118.         if(n2 % 17 == 0 || n2 == 224 || n2 == 611 || n2 == 424 || n2 == 982 || n2 == 61)
  119.             continue;
  120.  
  121.         newGraph[n1].push_back(n2);
  122.         newGraph[n2].push_back(n1);
  123.         edges++;
  124.     }
  125.  
  126.     cout << "\n" << edges << "\n";
  127.     numOfIsolates = 0;
  128.     for (int i = 0; i < 1000; i++) {
  129.         if (newGraph[i].empty()) {
  130.             if (!(i % 17 == 0 || i == 224 || i == 611 || i == 424 || i == 982 || i == 61)) {
  131.                 isolates[numOfIsolates++] = i;
  132.             }
  133.         }
  134.     }
  135.     cout << numOfIsolates << "\n";
  136.     for (int i = 0; i < numOfIsolates; i++) {
  137.         cout << isolates[i] << " ";
  138.     }
  139.     max = 0;
  140.     for (int i = 0; i < 1000; i++) {
  141.         if (newGraph[i].size() > max) {
  142.             maxNode = i;
  143.             max = newGraph[i].size();
  144.         }
  145.     }
  146.     cout << "\n";
  147.     cout << maxNode << " " << max << "\n";
  148.  
  149.  
  150.         for (int i = 0; i < 1000; i++) {
  151.         for (int j = 0; j < 1000; j++) {
  152.             if(!graph[i].empty() && !graph[j].empty() && i % 17 !=0 && j % 17 !=0) {
  153.                 vector<int> dist = bfs(graph, i, j);    //Use the BFS function to find the longest shortest path
  154.                 if (dist > maxDist) {
  155.                     maxDist = dist;
  156.                 }
  157.             }
  158.         }
  159.     }
  160.  
  161.     printPath(maxDist);
  162.  
  163.     path = bfs(newGraph, a, b);
  164.     printPath(path);
  165.     path.clear();
  166.     path = bfs(newGraph, c, d);
  167.     printPath(path);
  168.     path.clear();
  169.     path = bfs(newGraph, e, f);
  170.     printPath(path);
  171.  
  172.     return 0;
  173. }
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