Codrut Borcutean: Pagină nouă: == Cerinţa == Se dă un graf orientat cu '''n''' vârfuri și '''m''' arce prin lista arcelor și un număr natural '''k'''. Afișați numărul de vârfuri ale componentei tare conexe în care se află vârful '''k'''. == Date de intrare == Programul citește de la tastatură numărul '''n''' de noduri și numărul '''m''' de arce și numărul '''k''', iar apoi lista arcelor, formată din '''m''' perechi de forma '''i j''', cu semnificația că există arc orientat de la nod...

2024-01-04T15:52:24Z

Pagină nouă: == Cerinţa == Se dă un graf orientat cu '''n''' vârfuri și '''m''' arce prin lista arcelor și un număr natural '''k'''. Afișați numărul de vârfuri ale componentei tare conexe în care se află vârful '''k'''. == Date de intrare == Programul citește de la tastatură numărul '''n''' de noduri și numărul '''m''' de arce și numărul '''k''', iar apoi lista arcelor, formată din '''m''' perechi de forma '''i j''', cu semnificația că există arc orientat de la nod...

New page

== Cerinţa ==
Se dă un graf orientat cu '''n''' vârfuri și '''m''' arce prin lista arcelor și un număr natural '''k'''. Afișați numărul de vârfuri ale componentei tare conexe în care se află vârful '''k'''.
== Date de intrare ==
Programul citește de la tastatură numărul '''n''' de noduri și numărul '''m''' de arce și numărul '''k''', iar apoi lista arcelor, formată din '''m''' perechi de forma '''i j''', cu semnificația că există arc orientat de la nodul '''i''' la nodul '''j'''.
== Date de ieșire ==
Programul va afișa pe ecran numărul '''c''', reprezentând numărul de vârfuri ale componentei tare conexe în care se află vârful '''k'''.
== Restricţii şi precizări ==
* '''1 ≤ k ≤ n ≤ 100'''
== Exemplu 1 ==
; Intrare
8 12 3
1 3
3 5
5 7
7 1
2 6
6 8
8 2
1 4
4 6
4 8
4 2
1 8
; Iesire
Datele de intrare corespund restrictiilor impuse
4
<br>
== Exemplu 2 ==
; Intrare
0 0 0
; Iesire
Datele de intrare nu corespund restrictiilor impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
def dfs(graph, start):
# Inițializează stiva și setul de noduri vizitate
stack = [start]
visited = set()

while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
stack.extend(graph.get(node, []) - visited)

return visited

def verifica_restrictii(n, arce):
# Verifică dacă datele de intrare respectă restricțiile
if not (1 <= n <= 100) or not all(1 <= i <= n and 1 <= j <= n for i, j in arce):
return False
return True

def main():
n, m, k = map(int, input().split())
arce = [tuple(map(int, input().split())) for _ in range(m)]

# Verifică dacă datele de intrare respectă restricțiile
if not verifica_restrictii(n, arce):
print("Datele de intrare nu corespund restrictiilor impuse")
return

print("Datele de intrare corespund restrictiilor impuse")

# Construiește graful și graful transpus
graph = {}
graph_transposed = {}
for i, j in arce:
if i not in graph:
graph[i] = set()
if j not in graph_transposed:
graph_transposed[j] = set()
graph[i].add(j)
graph_transposed[j].add(i)

# Aplică DFS pe graful transpus pentru a găsi nodurile accesibile din nodul k
reachable_nodes = dfs(graph_transposed, k)

# Verifică dacă există un nod din care se poate ajunge în toate celelalte noduri
component_nodes = [node for node in range(1, n + 1) if node in dfs(graph, node) and node in reachable_nodes]

print(len(component_nodes))

if __name__ == "__main__":
main()

</syntaxhighlight>

3421 - ctck - Revision history