Барлыбай Мади, 311/312 группа WhatWhereWho 8158
Алмаз Сейтхазин (КФ МГУ, кафедра НДС) WhatWhereWho 7246
t1class UnknownError(Exception):t1class UnknownError(Exception):
2    pass2    pass
33
4class CycleError(Exception):4class CycleError(Exception):
5    pass5    pass
66
7class IneffectiveError(Exception):7class IneffectiveError(Exception):
8    pass8    pass
99
10def main():10def main():
11    plans = {}11    plans = {}
12    participants = []12    participants = []
13    while True:13    while True:
14        line = input().strip()14        line = input().strip()
15        if line == '':15        if line == '':
16            break16            break
17        parts = line.split(':', 1)17        parts = line.split(':', 1)
18        name = parts[0].strip()18        name = parts[0].strip()
19        participants.append(name)19        participants.append(name)
20        if len(parts) == 1 or parts[1].strip() == '':20        if len(parts) == 1 or parts[1].strip() == '':
21            plans[name] = []21            plans[name] = []
22        else:22        else:
23            plans[name] = [x.strip() for x in parts[1].split(',')]23            plans[name] = [x.strip() for x in parts[1].split(',')]
24    all_names = set(plans.keys())24    all_names = set(plans.keys())
25    for name, base_list in plans.items():25    for name, base_list in plans.items():
26        for base in base_list:26        for base in base_list:
27            if base not in all_names:27            if base not in all_names:
28                print('UNKNOWN')28                print('UNKNOWN')
29                return29                return
30    mros = {}30    mros = {}
31    in_progress = set()31    in_progress = set()
3232
33    def merge(sequences):33    def merge(sequences):
34        sequences = [seq[:] for seq in sequences if seq]34        sequences = [seq[:] for seq in sequences if seq]
35        result = []35        result = []
36        while any(sequences):36        while any(sequences):
37            found = None37            found = None
38            for seq in sequences:38            for seq in sequences:
39                if not seq:39                if not seq:
40                    continue40                    continue
41                candidate = seq[0]41                candidate = seq[0]
42                for other in sequences:42                for other in sequences:
43                    if candidate in other[1:]:43                    if candidate in other[1:]:
44                        candidate = None44                        candidate = None
45                        break45                        break
46                if candidate is not None:46                if candidate is not None:
47                    found = candidate47                    found = candidate
48                    break48                    break
49            if found is None:49            if found is None:
50                return None50                return None
51            result.append(found)51            result.append(found)
52            for seq in sequences:52            for seq in sequences:
53                if seq and seq[0] == found:53                if seq and seq[0] == found:
54                    del seq[0]54                    del seq[0]
55        return result55        return result
5656
57    def compute_mro(name):57    def compute_mro(name):
58        if name in mros:58        if name in mros:
59            return mros[name]59            return mros[name]
60        if name not in plans:60        if name not in plans:
61            raise UnknownError()61            raise UnknownError()
62        if name in in_progress:62        if name in in_progress:
63            raise CycleError()63            raise CycleError()
64        in_progress.add(name)64        in_progress.add(name)
65        bases = plans[name]65        bases = plans[name]
66        mros_bases = []66        mros_bases = []
67        for base in bases:67        for base in bases:
68            mro_base = compute_mro(base)68            mro_base = compute_mro(base)
69            mros_bases.append(mro_base)69            mros_bases.append(mro_base)
70        sequences = mros_bases + [bases]70        sequences = mros_bases + [bases]
71        merged = merge(sequences)71        merged = merge(sequences)
72        if merged is None:72        if merged is None:
73            raise IneffectiveError()73            raise IneffectiveError()
74        mro = [name] + merged74        mro = [name] + merged
75        mros[name] = mro75        mros[name] = mro
76        in_progress.remove(name)76        in_progress.remove(name)
77        return mro77        return mro
78    try:78    try:
79        for name in participants:79        for name in participants:
80            compute_mro(name)80            compute_mro(name)
81    except UnknownError:81    except UnknownError:
82        print('UNKNOWN')82        print('UNKNOWN')
83        return83        return
84    except CycleError:84    except CycleError:
85        print('CYCLE')85        print('CYCLE')
86        return86        return
87    except IneffectiveError:87    except IneffectiveError:
88        print('INEFFECTIVE')88        print('INEFFECTIVE')
89        return89        return
90    for name in participants:90    for name in participants:
91        mro = mros[name][1:]91        mro = mros[name][1:]
92        print(f"{name}: {', '.join(mro)}")92        print(f"{name}: {', '.join(mro)}")
93if __name__ == '__main__':93if __name__ == '__main__':
94    main()94    main()
Legends
Colors
 Added 
Changed
Deleted
Links
(f)irst change
(n)ext change
(t)op