M1

Matura 34a

63
Dla danej, dodatniej liczby całkowitej N, na kartce papieru rysujemy N różnych punktów
i numerujemy je liczbami 1, 2, ..., N. W tym zadaniu będziemy łączyć punkty ze sobą
strzałkami – funkcja strzałka(x,y) rysuje strzałkę od punktu o numerze x do punktu
o numerze y.
Wywołanie poniżej zapisanej funkcji rekurencyjnej rysuj(x) poskutkuje narysowaniem pewnej
liczby strzałek. Jej jedynym argumentem jest pewna liczba całkowita x z przedziału [1, N ].

W pliku pary.txt danych jest 1000 par liczb całkowitych z przedziału [1, 100 000], po
jednej parze w wierszu. Liczby w każdym wierszu są rozdzielone znakiem odstępu. Druga
liczba w parze zawsze jest większa od pierwszej.
Dla N = 100 000 wykonano polecenie rysuj(1) dla pewnego układu N punktów.
Napisz program, który znajdzie i wypisze te pary liczb z pliku pary.txt, które
odpowiadają numerom punktów x i y takich, że z punktu o numerze x można przejść po
jednej lub wielu strzałkach (zawsze zgodnie z ich zwrotami) do punktu o numerze y.
W odpowiedzi podaj liczbę par, które spełniają warunki zadania
rysunek.jpg pary.txt okregi.txt