#include <cstdio> using namespace std; int create_node(int *S,int M,int N) { // S[m] - count of nodes with m edges // M - number of edges in this node // N - number of this node int m,n = N+1; for (m = 0; m < M-2; m++) // -1 due to egde up -1 due to last edge (possible multiple) { printf("%d %d\n",N,n); //creating nodes with 1 edge S[1]--; n++; } printf("%d %d\n",N,n); //last edge for this node, possible with multiple edges S[M]--; m = M; while (m > 1 && S[m] == 0) m--; if (m > 1) n = create_node(S,m,n); return n; } int main() { int N,S[200001],s,M,m,R,x; scanf("%d",&N); for (int n = 0; n < N; n++) S[n] = 0; M = 0; R = 0; for (int n = 0; n < N; n++) { scanf("%d",&s); if (M < s) M = s; S[s]++; if (s > 2) R += s-2; } R += 2; // printf("Debug: S[1] = %d, R = %d\n",S[1],R); if (S[1] != R) { if (S[1] == 0) x = 2; else if (S[1] == 1) x = 1; else x = 0; printf("%d\n%d\n",x,2); printf("%d %d\n",1,2); // 1st node with 1 edge } else if (S[1] == R) { x = 0; printf("%d\n%d\n",x,N); printf("%d %d\n",1,2); // 1st node with 1 edge S[1]--; if (N > 2) create_node(S,M,2); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | #include <cstdio> using namespace std; int create_node(int *S,int M,int N) { // S[m] - count of nodes with m edges // M - number of edges in this node // N - number of this node int m,n = N+1; for (m = 0; m < M-2; m++) // -1 due to egde up -1 due to last edge (possible multiple) { printf("%d %d\n",N,n); //creating nodes with 1 edge S[1]--; n++; } printf("%d %d\n",N,n); //last edge for this node, possible with multiple edges S[M]--; m = M; while (m > 1 && S[m] == 0) m--; if (m > 1) n = create_node(S,m,n); return n; } int main() { int N,S[200001],s,M,m,R,x; scanf("%d",&N); for (int n = 0; n < N; n++) S[n] = 0; M = 0; R = 0; for (int n = 0; n < N; n++) { scanf("%d",&s); if (M < s) M = s; S[s]++; if (s > 2) R += s-2; } R += 2; // printf("Debug: S[1] = %d, R = %d\n",S[1],R); if (S[1] != R) { if (S[1] == 0) x = 2; else if (S[1] == 1) x = 1; else x = 0; printf("%d\n%d\n",x,2); printf("%d %d\n",1,2); // 1st node with 1 edge } else if (S[1] == R) { x = 0; printf("%d\n%d\n",x,N); printf("%d %d\n",1,2); // 1st node with 1 edge S[1]--; if (N > 2) create_node(S,M,2); } return 0; } |