D. Graph And Its Complement

Codeforces

IDCF990D

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsgraphsimplementation

English · Original

Chinese · Translation

Formal · Original

Given three numbers $n, a, b$. You need to find an adjacency matrix of such an undirected graph that the number of components in it is equal to $a$, and the number of components in its complement is $b$. The matrix must be symmetric, and all digits on the main diagonal must be zeroes. In an undirected graph loops (edges from a vertex to itself) are not allowed. It can be at most one edge between a pair of vertices. The adjacency matrix of an undirected graph is a square matrix of size $n$ consisting only of "0" and "1", where $n$ is the number of vertices of the graph and the $i$\-th row and the $i$\-th column correspond to the $i$\-th vertex of the graph. The cell $(i,j)$ of the adjacency matrix contains $1$ if and only if the $i$\-th and $j$\-th vertices in the graph are connected by an edge. A connected component is a set of vertices $X$ such that for every two vertices from this set there exists at least one path in the graph connecting this pair of vertices, but adding any other vertex to $X$ violates this rule. The complement or inverse of a graph $G$ is a graph $H$ on the same vertices such that two distinct vertices of $H$ are adjacent if and only if they are not adjacent in $G$. ## Input In a single line, three numbers are given $n, a, b \,(1 \le n \le 1000, 1 \le a, b \le n)$: is the number of vertexes of the graph, the required number of connectivity components in it, and the required amount of the connectivity component in it's complement. ## Output If there is no graph that satisfies these constraints on a single line, print "NO" (without quotes). Otherwise, on the first line, print "YES"(without quotes). In each of the next $n$ lines, output $n$ digits such that $j$\-th digit of $i$\-th line must be $1$ if and only if there is an edge between vertices $i$ and $j$ in $G$ (and $0$ otherwise). Note that the matrix must be symmetric, and all digits on the main diagonal must be zeroes. If there are several matrices that satisfy the conditions — output any of them. [samples]

给定三个数 $n, a, b$。你需要构造一个无向图的邻接矩阵，使得该图的连通分量个数为 $a$，其补图的连通分量个数为 $b$。矩阵必须对称，且主对角线上的所有元素必须为零。在无向图中不允许自环（从顶点到自身的边）。任意两个顶点之间最多只能有一条边。无向图的邻接矩阵是一个大小为 $n$ 的方阵，仅由 "0" 和 "1" 组成，其中 $n$ 是图的顶点数，第 $i$ 行和第 $i$ 列对应图的第 $i$ 个顶点。邻接矩阵的单元格 $(i, j)$ 包含 $1$ 当且仅当图中的第 $i$ 个顶点和第 $j$ 个顶点由一条边相连。连通分量是一个顶点集合 $X$，满足：对于该集合中的任意两个顶点，图中都存在至少一条路径连接它们；但向 $X$ 中添加任何其他顶点都会破坏这一性质。图 $G$ 的补图（或逆图）$H$ 是在相同顶点集上定义的图，其中 $H$ 中两个不同的顶点相邻当且仅当它们在 $G$ 中不相邻。在一行中给出三个数 $n, a, b thin (1 lt.eq n lt.eq 1000, 1 lt.eq a, b lt.eq n)$：分别是图的顶点数、图中所需的连通分量个数、以及其补图中所需的连通分量个数。如果不存在满足这些约束的图，则在一行中输出 "NO"（不含引号）。否则，第一行输出 "YES"（不含引号）。接下来的 $n$ 行中，每行输出 $n$ 个数字，使得第 $i$ 行的第 $j$ 个数字为 $1$ 当且仅当图 $G$ 中顶点 $i$ 和 $j$ 之间有边（否则为 $0$）。注意矩阵必须对称，且主对角线上的所有数字必须为零。如果存在多个满足条件的矩阵，输出任意一个即可。 ## Input 在一行中给出三个数 $n, a, b thin (1 lt.eq n lt.eq 1000, 1 lt.eq a, b lt.eq n)$：分别是图的顶点数、图中所需的连通分量个数、以及其补图中所需的连通分量个数。 ## Output 如果不存在满足这些约束的图，则在一行中输出 "NO"（不含引号）。否则，第一行输出 "YES"（不含引号）。接下来的 $n$ 行中，每行输出 $n$ 个数字，使得第 $i$ 行的第 $j$ 个数字为 $1$ 当且仅当图 $G$ 中顶点 $i$ 和 $j$ 之间有边（否则为 $0$）。注意矩阵必须对称，且主对角线上的所有数字必须为零。如果存在多个满足条件的矩阵，输出任意一个即可。 [samples]

Given $ n, a, b \in \mathbb{N} $ with $ 1 \leq n \leq 1000 $, $ 1 \leq a, b \leq n $, find a symmetric $ n \times n $ binary matrix $ A = (a_{ij}) $ such that: - $ a_{ii} = 0 $ for all $ i \in \{1, \dots, n\} $ (no loops), - $ a_{ij} = a_{ji} $ for all $ i, j \in \{1, \dots, n\} $ (undirected), - The graph $ G $ with adjacency matrix $ A $ has exactly $ a $ connected components, - The complement graph $ \overline{G} $ (adjacency matrix $ \overline{A} = J - I - A $, where $ J $ is the all-ones matrix and $ I $ is the identity matrix) has exactly $ b $ connected components. If no such matrix exists, output "NO". Otherwise, output "YES" followed by $ A $.

Samples

Input #1

3 1 2

Output #1

Input #2

3 3 3

Output #2

NO

API Response (JSON)

{
  "problem": {
    "name": "D. Graph And Its Complement",
    "description": {
      "content": "Given three numbers $n, a, b$. You need to find an adjacency matrix of such an undirected graph that the number of components in it is equal to $a$, and the number of components in its complement is $",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF990D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given three numbers $n, a, b$. You need to find an adjacency matrix of such an undirected graph that the number of components in it is equal to $a$, and the number of components in its complement is $...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定三个数 $n, a, b$。你需要构造一个无向图的邻接矩阵，使得该图的连通分量个数为 $a$，其补图的连通分量个数为 $b$。矩阵必须对称，且主对角线上的所有元素必须为零。\n\n在无向图中不允许自环（从顶点到自身的边）。任意两个顶点之间最多只能有一条边。\n\n无向图的邻接矩阵是一个大小为 $n$ 的方阵，仅由 \"0\" 和 \"1\" 组成，其中 $n$ 是图的顶点数，第 $i$ 行和第 $i$ 列对应...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given $ n, a, b \\in \\mathbb{N} $ with $ 1 \\leq n \\leq 1000 $, $ 1 \\leq a, b \\leq n $, find a symmetric $ n \\times n $ binary matrix $ A = (a_{ij}) $ such that:\n\n- $ a_{ii} = 0 $ for all $ i \\in \\{1, \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments