ShowMeCode.com your best assistant in storage of text pieces.
Share code, evolve articles, or do whatever you can think of.
Upload file

C++: No Title

Number of lines: 248

0
rating

398 code views

  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
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
#include <stdio.h>

/*
    defines
*/

#define MAX_SCHOOLS         100
#define CONNECT             1
#define DISCONNECT          0
#define INVALID_COMPONENT   -1

/*
    input and input related data
*/

int N;
int A[MAX_SCHOOLS + 1][MAX_SCHOOLS + 1];    /* these things are easily understood ... */

void input() {
    FILE * in = fopen("input.txt", "rt");
    fscanf(in, "%d", &N);
    for (int i = 1; i <= N; i++) {
        A[i][i] = CONNECT;
        int j; fscanf(in, "%d", &j);
        while (j) {
            A[i][j] = CONNECT;
            fscanf(in, "%d", &j);
        }
    }
    fclose(in);
}

/*
    solve function and solving related data
*/

int task1[MAX_SCHOOLS + 1];                 /* answer for the 1st task */
int marked[MAX_SCHOOLS + 1];                /* markers for the 1st task */

int n_components;                           /* number of strongly connected components */
int representer[MAX_SCHOOLS + 1];           /* vertex that represents the component */
int domain[MAX_SCHOOLS + 1];                /* component number of the vertex */

int inputs_c;                               /* number of pure inputs */
int inputs_l[MAX_SCHOOLS + 1];              /* the list of pure inputs */

int is_remained_input[MAX_SCHOOLS + 1];     /* whether the input should be linked at the end */
int is_output[MAX_SCHOOLS + 1];             /* whether the component is pure output */

int stack_c;                                /* number of elements in stack */
int stack_l[MAX_SCHOOLS + 1];               /* stack for dfs */

int locked[MAX_SCHOOLS + 1];                /* whether the component is locked */

int added_l;                                /* number of the links added */
int W[MAX_SCHOOLS + 1][MAX_SCHOOLS + 1];    /* matrix of the links added */

/* adds an unexisting link. the algorithm is bugful if already exists */

void add_link(int i, int j) {
    if ((W[representer[i]][representer[j]] == CONNECT) || (A[representer[i]][representer[j]] == CONNECT)) {
        printf("error: link (%d -> %d) already exists.\n", i, j);
    } else {
        added_l++;
        W[representer[i]][representer[j]] = CONNECT;
        is_output[i] = 0;
        is_remained_input[j] = 0;
    }
}

void solve() {

    /* floyd-warshall comes ... */
    
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                A[i][j] |= A[i][k] & A[k][j];
    }
    
    /* task 1 */
    
    for (int i = 1; i <= N; i++) {
        if (!marked[i]) {
            task1[i] = 1;
            for (int j = 1; j <= N; j++) {
                marked[j] |= A[i][j];
                task1[j] &= !A[i][j] | (i == j);
            }
        }
    }
    
    /* now we have the 1st task solved. let's compute the strongly connected components ... */
    
    n_components = 0;
    for (int i = 1; i <= N; i++) {
        if (domain[i] == 0) {
            representer[n_components++] = i;
            for (int j = 1; j <= N; j++)
                if (A[i][j] && A[j][i]) {
                    domain[j] = i;
                }
        }
    }
    
    /* ok. now we must now whether the component is pure input or pure output ... */
    
    for (int i = 0; i < n_components; i++) {
        int is_input = 1; is_output[i] = 1;
        for (int j = 0; j < n_components; j++) {
            if (i == j)
                continue;
                
            if (A[representer[i]][representer[j]]) {
                is_output[i] = 0;
            }
            if (A[representer[j]][representer[i]])
                is_input = 0;
        }
        is_remained_input[i] = is_input;
        if (is_input)
            inputs_l[inputs_c++] = i;
    }
    
    /*
        we`ll need two vertices on the One Great Cycle somewhere below ...
    */
    
    int cycle_in = INVALID_COMPONENT, cycle_out = INVALID_COMPONENT;
    
    /*
        well. we`ve just divided all the components into pure inputs, pure outputs and some other garbage.
        now we`ll construct a Large Hadron Collider. :) that will be some cycle through all the 
        pseudo-trees ...
    */
    
    int first_input = inputs_c == 0 ? INVALID_COMPONENT : inputs_l[inputs_c - 1];
    int prev_output = INVALID_COMPONENT;
    
    while (inputs_c > 0) {
        int input_c = inputs_l[--inputs_c];
        
        /* we`ll use depth-first search to go down locking passed vertices */
        int found_output = INVALID_COMPONENT;
        
        stack_l[stack_c++] = input_c;
        
        while (stack_c > 0) {
            int c = stack_l[--stack_c];
            
            locked[c] = 1;
            
            if (is_output[c]) {
                /* found some pure output. stopping dfs ... */
                found_output = c;
                stack_c = 0;
                break;
            } else {
                /* going further ... */
                for (int i = 0; i < n_components; i++)
                    if (!locked[i] && (A[representer[c]][representer[i]] == CONNECT))
                        stack_l[stack_c++] = i;
            }
        }
        
        /* link previous output (if any) to the input */
        if (found_output != INVALID_COMPONENT) {
            if (prev_output != INVALID_COMPONENT) {
                add_link(prev_output, input_c);

                cycle_in = input_c; cycle_out = prev_output;
            }
            prev_output = found_output;
        }
    }

    /* and link the last to the first if possible */
    if ((first_input != INVALID_COMPONENT) && (prev_output !=  first_input)) {
        add_link(prev_output, first_input);
        
        cycle_in = first_input; cycle_out = prev_output;
    }
        
    /*
        well, well, well, ... now we have the One Large Cycle and (maybe) some pure inputs and
        pure outputs. we should link them in pairs ...
    */
    
    for (int k = 0; k < n_components; k++)
        for (int p = 0; p < n_components; p++) {
            if (k == p)
                continue;
            if (is_output[k] && is_remained_input[p]) {
                add_link(k, p);
                
                cycle_in = p; cycle_out = k;
            }
        }
    
    /* and now link others to the One Large Cycle ... */
    
    for (int k = 0; k < n_components; k++) {
        if (is_output[k] && !is_remained_input[k]) {
            add_link(k, cycle_in);
        }
    }
    
    for (int k = 0; k < n_components; k++) {
        if (is_remained_input[k] && !is_output[k]) {
            add_link(cycle_out, k);
        }
    }
    
    /* we assume that the task is solved ;) */
}

/*
    just the output function
*/

void output() {
    FILE * out = fopen("output.txt", "wt");

    int counter = 0;
    for (int i = 1; i <= N; i++)
        counter += task1[i];
    fprintf(out, "%d\n", counter);
    
    fprintf(out, "%d\n", added_l);
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) 
            if (W[i][j] == CONNECT)
                fprintf(out, "%d %d\n", i, j);
        
    fclose(out);
}

/*
    main function
*/

int main(void) {
    input();
    solve();
    output();

    return 0;
}

Description:

No decription given
image

Posted by: eigenein

2010.04.13 - 21:06

Code Revisions

#latest

Permalink: