SHARE
TWEET

Untitled

a guest May 8th, 2020 110 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. A company offers personal computers for sale inNtowns (3<=N<=35). The towns are denoted by 1,2,...,N. There are direct routes connecting M pairs from among these towns. The company decides to build servicing stations in several towns, so that for any town X, there would be a station locatedeither in X or in some immediately neighbouring town of X.
  2. Write a program for finding out the minumum number of stations, which the company has to build,so that the above condition holds.
  3. Input
  4. The input consists of more than one description of town (but totally, less than ten descriptions). Everydescription starts with number N of towns and number M of pairs of towns directly connected each other. The integers N and M are separated by a space. Every one of the next M rows contains a pair of connected towns, one pair per row. The pair consists of two integers for town's numbers, separated by a space. The input ends with N = 0 and M = 0.
  5. Output
  6. For every town in the input write a line containing the obtained minimum.
  7.  
  8. Sample Input
  9. 8 12
  10. 1 2
  11. 1 6
  12. 1 8
  13. 2 3
  14. 2 6
  15. 3 4
  16. 3 5
  17. 4 5
  18. 4 7
  19. 5 6
  20. 6 7
  21. 6 8
  22. 0 0
  23.  
  24. Sample Output
  25. 2
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