Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Algo : BCC
- low[u] = min(low[u], low[v]);
- if (u != root && dis[u] <= low[v]) {
- total_node.clear();
- while (!BCC.empty()) {
- int x = BCC.top().u;
- int y = BCC.top().v;
- cout << x << " " << y << endl;
- BCC.pop();
- if (x == u && y == v)
- break;
- }
- }
- }
- else {
- low[u] = min(low[u], dis[v]);
- }
- }
- }
- void BCC_ALL() {
- memset(vis, 0, sizeof vis);
- for (int i = 0; i < tNode; i++) {
- if (vis[i])
- continue;
- timer = 1; child = 0; root = i;
- dfs(root);
- total_node.clear();
- while (!BCC.empty()) {
- int x = BCC.top().u;
- int y = BCC.top().v;
- cout << x << " " << y << endl;
- BCC.pop();
- }
- }
- }
- // Algorithm : Havel Hakimi
- // Complexity : O(n^2 log(n))
- int arr[mx], n; // n : Number of Node
- bool Havel_Hakimi() {
- for (int i=0; i<n-1; i++) {
- sort(arr+i, arr+n, greater <int> ());
- for (int j=i+1; j<=i+arr[i]; j++) {
- arr[j]--;
- if (arr[j] < 0) return false;
- }
- }
- if (arr[n-1] != 0) return false;
- return true;
- }
- int main() {
- while (cin >> n, n) {
- bool flag = true;
- int sumOfDegree = 0;
- for (int i=0; i<n; i++) {
- cin >> arr[i];
- if (arr[i] >= n || arr[i]<0)
- flag = false;
- sumOfDegree += arr[i];
- }
- if (sumOfDegree & 1)
- cout << "Not possible" << endl;
- else if (!flag || !Havel_Hakimi())
- cout << "Not possible" << endl;
- else
- cout << "Possible" << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement