Cod sursa(job #3233947)

Utilizator marincodeazaGeorgescu Radu Andrei marincodeaza Data 5 iunie 2024 15:17:18
Problema Sortare topologica Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <stdio.h>
#include <stdlib.h>

int main()
{

    int n, m;
    FILE *in = fopen("sortare.in", "r");
    FILE *out = fopen("sortare.out", "w");
    fscanf(in, "%d %d", &n, &m);
    int mat[100][100] = {0}, x, y;
    for(int i = 0; i < m; i++) {
        fscanf(in, "%d%d", &x, &y);
        mat[x][y] = 1;
    }
    int sol[100];
    int avail[100] = {0};
    int grade[100] = {0};
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) {
            if(mat[j][i] == 1)
                grade[i]++;
        }
    int k = 0;
    for(int i = 0; i < n - 1; i++)
        if(grade[i] == 0)
            avail[k++] = i;
    int isol = 0;
    while(k > 0) {
        int copy = avail[0];
        sol[isol] = copy;
        isol++;

          for(int i = 0; i < k - 1; i++) 
                avail[i] = avail[i + 1];
            k--;

            for(int i = 0; i < n; i++)
                if(mat[copy][i] == 1) {
                    mat[copy][i] = 0;
                    int ok = 1;
                    for(int j = 0; j < n; j++)
                        if(mat[j][i] == 1)
                            ok = 0;

                    if(ok == 1)
                        avail[k++] = i;
                }      
    }
    int iszero = 1;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(mat[i][j] == 1)
                iszero = 0;
    if(iszero == 0)
        printf("Ups!");
    else {
        for(int i = 0; i < isol; i++)
            fprintf(out, "%d ", sol[i]);
    }
        


}