Programozó versenyek

DEIK Regionális Programozó Csapatverseny, egyetemi kategória, 2022. december 4.

2022. december 4. 10:00 – 2022. december 4. 15:15

jövőbeli barátok

Egy csoportban a tagok vagy baráti vagy ellenséges vagy semleges viszonyban vannak egymással (minden viszony kölcsönös!). Lehetséges azonban hogy bizonyos párok esetén a jövőben barátság alakul ki. Egyes tudósok szerint ha A és B semleges viszonyban vannak, viszont el lehet jutni A-tól B-ig baráti kapcsolatok sorozatán keresztül, akkor A és B a jövőben barátok lesznek, ezért A-t és B-t jövőbeli barát-oknak nevezzük.

Például ha egy négyfős csoportban az (1,2), (1,3), (2,4) párok baráti és a (3,4) pár ellenséges viszonyban van, akkor a fenti ábra bal oldali része írja le a jelenlegi helyzetet, zöld és piros éleket használva a baráti és az ellenséges kapcsolatok jelzésére (a semleges viszonyt az él hiány jelzi). A jövőbeli barátok az ábra jobboldali részében láthatók szagatott zöld éllel összekötve:

    1 és 4 semleges viszonyban vannak, de az 1 -> 2 -> 4 baráti út összeköti őket
    2 és 3 semleges viszonyban vannak, de az 2 -> 1 -> 3 baráti út összeköti őket
    a 3 és 4 között is vezet zöld út, ám ők ellenségek
Megállapíthatjuk hogy minden tagnak 1 jövőbeli barátja van, így a jövőbeli barátok átlagos száma a csoportban 1

Feladat: Adott csoportbeli viszonyok esetén számoljuk ki a jövőbeli barátok átlagos számát (M) számát.

A bemenet specifikációja


N B E
x1 y1
...
xB yB
u1 v1
...
uE vE

Az első sorban vannak a 1 ≤ N,B,E ≤ 104 szóközzel elválasztott számok, melyek rendre a csoport tagjainak, a baráti viszonyoknak és az ellenséges viszonyoknak a száma. A következő B sorban található számpárok a baráti, az ezt követő E sorban levő számpárok az ellenséges viszonyokat írják le. Minden a viszonyokat leíró sorban szóközzel elválasztott, különböző, 1 és N közötti számok. Egy viszony legfeljebb egyszer szerepel az adatok közt.

A kimenet specifikációja

M

Egyetlen sor a keresett átlagos számmal, melyet 6 jegyre kerekítve írjunk ki.

1. példa bemenet

  1. 4 3 1
  2. 1 2
  3. 3 1
  4. 2 4
  5. 3 4
letöltés szöveges állományként

1. példa kimenet

  1. 1.000000
letöltés szöveges állományként

2. példa bemenet

  1. 2 0 0
letöltés szöveges állományként

2. példa kimenet

  1. 0.000000
letöltés szöveges állományként

3. példa bemenet

  1. 4 4 1
  2. 2 1
  3. 1 3
  4. 3 2
  5. 3 4
  6. 4 1
letöltés szöveges állományként

3. példa kimenet

  1. 0.500000
letöltés szöveges állományként
Debreceni Egyetem, Informatikai Kar, v. 2019.03.01.