fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define in_range(x,y,z) for(int x=y; x<z; x++)
  5.  
  6. int main()
  7. {
  8. int m,n;
  9. cin >> n >> m;
  10. vector < vector<int> > g(n); // граф
  11. int s=0; // начальная вершина
  12. in_range(i,0,m) // считывание графа
  13. {
  14. int u,v;
  15. cin >> u >> v;
  16. g[u-1].push_back(v-1);
  17. g[v-1].push_back(u-1);
  18. }
  19. queue<int> q; // очередь с вершинами, которые мы рассматриваем на данном этапе
  20. q.push (s);
  21. vector<bool> used (n); // логический массив, указывающий, посещена ли вершина
  22. used[s] = true;
  23. while (!q.empty()) // пока мы не обойдем все вершины, которые можно достигнуть из данной
  24. {
  25. int v = q.front();
  26. q.pop(); // достаем из очереди одну вершину
  27. for (size_t i=0; i<g[v].size(); ++i) //просмотрим все ребра, исходящие из данной вершины
  28. {
  29. int to = g[v][i];
  30. if (!used[to]) //если текущая вершина еще не была посещена
  31. {
  32. used[to] = true; //отимечаем, что мы ее посетили
  33. q.push (to); // помещаем в очередь
  34. }
  35. }
  36. }
  37. vector<bool>::iterator it;
  38. it = find (used.begin(), used.end(), false); // проверяем, остались ли еще непосещенные вершины
  39. if (it == used.end()) cout << "YES"; // если все вершины, посещены, то граф связный
  40. else cout << "NO";
  41. return 0;
  42. }
  43.  
Success #stdin #stdout 0s 3420KB
stdin
3 2
1 2
3 2
stdout
YES