H. Control

Codeforces

IDCF10100H

Time2000ms

Memory28MB

Difficulty—

English · Original

Formal · Original

You are given a directed graph with nodes and edges. You can say that node controls node if you can reach node from node only using the edges in the graph. For each node in the graph, you must print the number of nodes that node controls. The first line contains (), the number of nodes. lines follow. Each line starts with a number , followed by numbers, representing the nodes that has an edge to. It is guaranteed that the sum of the numbers is less than . Also, there are no more than maximal subsets of nodes such that for any edge in the subset, there is a series of edges connecting with . You must print numbers on the first line, separated by a blank space, where the th number represents the number of nodes controlled by . ## Input The first line contains (), the number of nodes. lines follow. Each line starts with a number , followed by numbers, representing the nodes that has an edge to. It is guaranteed that the sum of the numbers is less than . Also, there are no more than maximal subsets of nodes such that for any edge in the subset, there is a series of edges connecting with . ## Output You must print numbers on the first line, separated by a blank space, where the th number represents the number of nodes controlled by . [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of nodes. Let $ G = (V, E) $ be a directed graph, where $ V = \{1, 2, \dots, n\} $ and $ E \subseteq V \times V $. For each node $ u \in V $, define the set of nodes controlled by $ u $ as: $$ C(u) = \{ v \in V \mid \text{there exists a directed path from } u \text{ to } v \} $$ **Constraints** 1. The input is given as $ n $ lines; for each node $ i \in V $, a list of out-neighbors is provided. 2. The total number of edges satisfies $ |E| < \text{some bound} $ (not used in formalism). 3. The graph has at most a constant number of strongly connected components (not used in formalism). **Objective** For each node $ i \in V $, compute $ |C(i)| $, and output the sequence $ \left( |C(1)|, |C(2)|, \dots, |C(n)| \right) $.

API Response (JSON)

{
  "problem": {
    "name": "H. Control",
    "description": {
      "content": "You are given a directed graph with  nodes and  edges. You can say that node  controls node  if you can reach node  from node  only using the edges in the graph. For each node  in the graph, you must ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 28672
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10100H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a directed graph with  nodes and  edges. You can say that node  controls node  if you can reach node  from node  only using the edges in the graph. For each node  in the graph, you must ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of nodes.  \nLet $ G = (V, E) $ be a directed graph, where $ V = \\{1, 2, \\dots, n\\} $ and $ E \\subseteq V \\times V $.  \nFor each node $ u \\in ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments