• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Sortowanie topologiczne c++

Object Storage Arubacloud
0 głosów
230 wizyt
pytanie zadane 10 lutego 2021 w C i C++ przez KumberTwo Dyskutant (8,270 p.)

Piszę najprostszą - zupełnie podstawową wersję sortowania topologicznego. Dla małych grafów na których sprawdzałem program wszystko wydaje się działać dobrze. Niestety dla testu z zadania odpowiedź jest niepełna. Mógłby ktoś podpowiedzieć, co tu nie działa?

#include <bits/stdc++.h>
using namespace std;

vector<int> krawedzie[100007];
queue<int> kolejka;
int ile_laczen[100007];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int ile_wierz, ile_kraw;
    cin >> ile_wierz >> ile_kraw;
    for(int i = 1; i <= ile_kraw; i++)
    {
        int a, b;
        cin >> a >> b;
        krawedzie[a].push_back(b);
        ile_laczen[b]++;
    }

    for(int i = 1; i <= ile_wierz; i++)
    {
        if(ile_laczen[i] == 0)
        {
            kolejka.push(i);
            break;
        }
    }
    //cout << "ODP: ";
    while(!kolejka.empty())
    {
        int teraz = kolejka.front();
        kolejka.pop();
        cout << teraz << " ";
        //cout << "mam " << krawedzie[teraz].size() << " krawedzi\n";
        for(int i = 0; i < krawedzie[teraz].size(); i++)
        {
            ile_laczen[krawedzie[teraz][i]]--;
            if(ile_laczen[krawedzie[teraz][i]] <= 0)
            {
                kolejka.push(krawedzie[teraz][i]);
            }
        }
    }
}

/*
test:
15 15
7 12
5 13
9 10
8 13
9 4
12 1
2 10
12 14
12 13
6 5
15 14
1 13
8 6
3 15
11 2

poprawna odpowiedz:
11 9 8 7 12 6 5 4 3 15 14 2 10 1 13
*/

Na dole w komentarzu jest test, na którym program nie działa oraz poprawna odpowiedź do niego.

1 odpowiedź

+1 głos
odpowiedź 10 lutego 2021 przez Whistleroosh Maniak (56,980 p.)
wybrane 10 lutego 2021 przez KumberTwo
 
Najlepsza
W linii 28 nie powinno być breaka
komentarz 10 lutego 2021 przez KumberTwo Dyskutant (8,270 p.)
Program dostał 100 pkt :) dziękuję za pomoc

Podobne pytania

0 głosów
0 odpowiedzi 247 wizyt
pytanie zadane 7 stycznia 2023 w C i C++ przez polandonion Mądrala (7,140 p.)
+2 głosów
1 odpowiedź 824 wizyt
pytanie zadane 4 czerwca 2017 w C i C++ przez Wiciorny Ekspert (271,430 p.)
0 głosów
1 odpowiedź 541 wizyt
pytanie zadane 14 stycznia 2023 w C i C++ przez polandonion Mądrala (7,140 p.)

92,654 zapytań

141,543 odpowiedzi

319,954 komentarzy

62,022 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...