Advertisement
dipBRUR

25

Nov 19th, 2017
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.69 KB | None | 0 0
  1. // Algo : BCC
  2. low[u] = min(low[u], low[v]);
  3. if (u != root && dis[u] <= low[v]) {
  4. total_node.clear();
  5. while (!BCC.empty()) {
  6. int x = BCC.top().u;
  7. int y = BCC.top().v;
  8. cout << x << " " << y << endl;
  9. BCC.pop();
  10. if (x == u && y == v)
  11. break;
  12. }
  13. }
  14. }
  15. else {
  16. low[u] = min(low[u], dis[v]);
  17. }
  18. }
  19. }
  20. void BCC_ALL() {
  21. memset(vis, 0, sizeof vis);
  22. for (int i = 0; i < tNode; i++) {
  23. if (vis[i])
  24. continue;
  25. timer = 1; child = 0; root = i;
  26. dfs(root);
  27. total_node.clear();
  28. while (!BCC.empty()) {
  29. int x = BCC.top().u;
  30. int y = BCC.top().v;
  31. cout << x << " " << y << endl;
  32. BCC.pop();
  33. }
  34. }
  35. }
  36.  
  37. // Algorithm : Havel Hakimi
  38. // Complexity : O(n^2 log(n))
  39.  
  40. int arr[mx], n; // n : Number of Node
  41. bool Havel_Hakimi() {
  42. for (int i=0; i<n-1; i++) {
  43. sort(arr+i, arr+n, greater <int> ());
  44. for (int j=i+1; j<=i+arr[i]; j++) {
  45. arr[j]--;
  46. if (arr[j] < 0) return false;
  47. }
  48. }
  49. if (arr[n-1] != 0) return false;
  50. return true;
  51. }
  52.  
  53. int main() {
  54. while (cin >> n, n) {
  55. bool flag = true;
  56. int sumOfDegree = 0;
  57. for (int i=0; i<n; i++) {
  58. cin >> arr[i];
  59. if (arr[i] >= n || arr[i]<0)
  60. flag = false;
  61. sumOfDegree += arr[i];
  62. }
  63. if (sumOfDegree & 1)
  64. cout << "Not possible" << endl;
  65. else if (!flag || !Havel_Hakimi())
  66. cout << "Not possible" << endl;
  67. else
  68. cout << "Possible" << endl;
  69. }
  70. return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement