[shkola] 1022

Taq zadacha sym q reshaval i daje sme q obsyjdali minalata godina. Dokolkoto si
spomnqm tva be6e topologichno sortirane. Pratam si minalogodishnoto reshenie
(togava oshte ne znaeh shto tui jivotno topologichno sortirane i napisah neshto
koeto mai se okazva takova). To ne e mnogo dobro i smqtam da go pooptimiziram
ama za sq pra6tam nego.
{Boqn}
<pre>
--------------------------------------
Това писмо е изпратено от  www.mail.bg

Безплатният адрес в mail.bg предлага:
- Силна АнтиСПАМ защита
- 12MB място за поща
- SMS за ново писмо (всички оператори)
- WAP достъп от GSM и без компютър
- Безплатен POP3 достъп
- Безплатна поддръжка по телефона
______________________________________
БЕЗ ИЗЛИШНИ ВЪПРОСИ РЕГИСТРИРАЙТЕ СВОЙ
БЕЗПЛАТЕН АДРЕС НА  http://www.mail.bg
</pre>


#include <iostream.h>
#define MAX 128


int mart[MAX][MAX];
int n;

void bfs(int start)
{       int i,qe,qb,c = n;
        int que[MAX*MAX] = {0};
        
        qb = qe = 0;
        
        que[qe++] = start;
        
        do
        {       for (i = 1; i <= n; i++)
                {       if (mart[que[qb]][i] == 1) 
                        {  que[qe++] = i;
                        }
                }
                qb++;
        } while (qe > qb);      
        /*      
        for (i = 0; i < qe; i++)
                cout << que[i] << " ";
        cout << '\n';
        */

        for (i = qe - 1; i >= 0; i--)
                if (!mart[que[i]][0]) 
                {       mart[que[i]][0] = 1; 
                        mart[0][c--] = que[i]; 
                }
        for (i = 1; i <= n; i++)
                cout << mart[0][i] << " ";
        cout << "\n";
        
}
int main()
{       int i,x,j,f = 0,start = 1;
        
        cin >> n;
        
        for (i = 1; i <= n; i++)
        {       do
                { cin >> x;
                  if (x) 
                  {      mart[i][x] = 1;
                         mart[x][i] = -1;
                  }
                } while (x != 0);
        }
        
        /*      
        for (i = 1; i <= n; i++)
        {       for (j = 1; j <= n; j++)
                        cout << mart[i][j] << " ";
                cout << "\n";
        }
        */
        
        for (i = 1; i <= n; i++)
        {       f = 0;
                for (j = 1; j <= n; j++)
                {       if (mart[i][j] == -1)
                        {       f = 1;
                                break;
                        }
                }
                if (f == 0) 
                {  start = i;
                   break;
                }
        }
        
        bfs(start);
        
        return 0;
}

Other related posts: