fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long int
  5. #define MOD 1000000007
  6.  
  7. int main(){
  8. #ifndef ONLINE_JUDGE
  9. freopen("input.txt", "r", stdin);
  10. freopen("output.txt", "w", stdout);
  11. #endif
  12.  
  13. ios_base::sync_with_stdio(false);
  14. cin.tie(NULL); cout.tie(NULL);
  15.  
  16. int testcase = 0;
  17. cin >> testcase;
  18.  
  19. while (testcase--) {
  20. int n, m;
  21. cin >> n >> m;
  22.  
  23. vector<vector<int>> G(n + 1); // 1-indexed graph
  24.  
  25. for (int i = 1; i <= m; i++) {
  26. int x, y;
  27. cin >> x >> y;
  28. if (x <= n && y <= n) { // Check if both nodes are within valid range
  29. G[x].push_back(y);
  30. G[y].push_back(x); // Undirected graph
  31. }
  32. }
  33.  
  34. int source;
  35. cin >> source;
  36.  
  37. queue<int> q;
  38. q.push(source);
  39.  
  40. vector<int> used(n + 1, 0); // Visited nodes
  41. used[source] = 1;
  42.  
  43. vector<int> lvl(n + 1, -1); // Level array, -1 means unvisited
  44. lvl[source] = 0; // Source node has level 0
  45.  
  46. while (!q.empty()) {
  47. int v = q.front();
  48. q.pop();
  49. for (auto x : G[v]) {
  50. if (used[x] == 0) {
  51. q.push(x);
  52. used[x] = 1;
  53. lvl[x] = lvl[v] + 1; // Distance from source
  54. }
  55. }
  56. }
  57.  
  58. // Print the answers for each node (1 to n)
  59. for (int i = 1; i <= n; i++) {
  60. if (used[i] == 0) {
  61. cout << "No ";
  62. } else {
  63. cout << "Yes ";
  64. }
  65. }
  66. cout << "\n"; // Newline after each test case
  67. }
  68.  
  69. return 0;
  70. }
  71.  
Success #stdin #stdout 0.01s 5288KB
stdin
1
5 4
1 2
2 3
2 4
6 7
2
stdout
Yes Yes Yes Yes No