Advertisement
Guest User

Untitled

a guest
Sep 22nd, 2019
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.09 KB | None | 0 0
  1. #include <fstream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. ifstream f("componenteconexe.in");
  6. ofstream of("componenteconexe.out");
  7.  
  8. int n, viz[101], viz1[101];
  9. bool a[101][101];
  10. queue <int> coada;
  11. priority_queue <int, vector<int>, greater<int>> coada1;
  12.  
  13. void dfs1(int nod) {
  14. //of << nod << " ";
  15. viz1[nod] = 1;
  16.  
  17. for (int i = 1; i <= n; i++)
  18. if (a[nod][i] && !viz1[i]) dfs1(i);
  19. }
  20.  
  21. void bfs(int nod) {
  22. viz[nod] = 1;
  23. coada.push(nod);
  24.  
  25. while (!coada.empty()) {
  26. for (int i = 1; i <= n; i++) {
  27. if (a[coada.front()][i] && !viz[i])
  28. viz[i] = 1, coada.push(i);
  29. }
  30. coada1.push(coada.front());
  31. coada.pop();
  32. }
  33. }
  34.  
  35. int main() {
  36. int c, b, i, cnt = 0;
  37. f >> n;
  38.  
  39. if (n == 1) {
  40. of << 1 << endl;
  41. of << 1;
  42. return 0;
  43. }
  44.  
  45. for (i = 0; i < n; i++) {
  46. f >> c >> b;
  47. a[c][b] = true;
  48. a[b][c] = true;
  49. }
  50.  
  51. for (i = 1; i <= n; i++)
  52. if (!viz1[i]) cnt++, dfs1(i);
  53.  
  54. of << cnt << endl;
  55. for (i = 1; i <= n; i++)
  56. if (!viz[i]) {
  57. bfs(i);
  58. while (!coada1.empty())
  59. of << coada1.top() << " ", coada1.pop();
  60. of << endl;
  61. }
  62.  
  63. return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement