fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. void bfs(int start, int n, const vector<vector<int>>& adj, vector<bool>& visited) {
  8. queue<int> q;
  9. q.push(start);
  10. visited[start] = true;
  11.  
  12. while (!q.empty()) {
  13. int node = q.front();
  14. q.pop();
  15.  
  16. for (int neighbor : adj[node]) {
  17. if (!visited[neighbor]) {
  18. visited[neighbor] = true;
  19. q.push(neighbor);
  20. }
  21. }
  22. }
  23. }
  24.  
  25. int main() {
  26. int n;
  27. cin >> n;
  28.  
  29. vector<vector<int>> adj(n + 1);
  30.  
  31. // Reading the edges
  32. while (true) {
  33. int p;
  34. cin >> p;
  35. if (p == 0) break;
  36.  
  37. int q;
  38. while (true) {
  39. cin >> q;
  40. if (q == 0) break;
  41. adj[p].push_back(q);
  42. }
  43. }
  44.  
  45. int k;
  46. cin >> k;
  47.  
  48. vector<int> startVertices(k);
  49. for (int i = 0; i < k; ++i) {
  50. cin >> startVertices[i];
  51. }
  52.  
  53. // For each starting vertex, perform BFS and print unreachable vertices
  54. for (int i = 0; i < k; ++i) {
  55. int start = startVertices[i];
  56. vector<bool> visited(n + 1, false);
  57.  
  58. bfs(start, n, adj, visited);
  59.  
  60. vector<int> unreachable;
  61. for (int j = 1; j <= n; ++j) {
  62. if (!visited[j]) {
  63. unreachable.push_back(j);
  64. }
  65. }
  66.  
  67. if (unreachable.empty()) {
  68. cout << "0" << endl;
  69. } else {
  70. for (int j = 0; j < unreachable.size(); ++j) {
  71. cout << unreachable[j];
  72. if (j != unreachable.size() - 1) cout << " ";
  73. }
  74. cout << endl;
  75. }
  76. }
  77.  
  78. return 0;
  79. }
  80.  
Success #stdin #stdout 0.03s 25764KB
stdin
5
1 2 3 0
2 4 5 0
3 0
4 0
5 0
2
1 3
stdout
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

void bfs(int start, int n, const vector<vector<int>>& adj, vector<bool>& visited) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> adj(n + 1);
    
    // Reading the edges
    while (true) {
        int p;
        cin >> p;
        if (p == 0) break;
        
        int q;
        while (true) {
            cin >> q;
            if (q == 0) break;
            adj[p].push_back(q);
        }
    }

    int k;
    cin >> k;
    
    vector<int> startVertices(k);
    for (int i = 0; i < k; ++i) {
        cin >> startVertices[i];
    }

    // For each starting vertex, perform BFS and print unreachable vertices
    for (int i = 0; i < k; ++i) {
        int start = startVertices[i];
        vector<bool> visited(n + 1, false);
        
        bfs(start, n, adj, visited);
        
        vector<int> unreachable;
        for (int j = 1; j <= n; ++j) {
            if (!visited[j]) {
                unreachable.push_back(j);
            }
        }
        
        if (unreachable.empty()) {
            cout << "0" << endl;
        } else {
            for (int j = 0; j < unreachable.size(); ++j) {
                cout << unreachable[j];
                if (j != unreachable.size() - 1) cout << " ";
            }
            cout << endl;
        }
    }

    return 0;
}