BZOJ3563 DZY Loves Chinese

Luogu

IDLGP10774

Time1000ms

Memory512MB

Difficulty—

线性基

给定无向图 $G = (V, E)$，$q$ 次询问每次给定一个边集，求删除该边集后图是否连通。保证边集大小不超过 $15$。强制在线。 ## Input 第一行输入两个正整数 $n,m$，表示图的结点数和边数。接下来 $m$ 行，每行两个正整数 $u_i,v_i$，表示第 $i$ 条边。接下来输入一行 $Q$，表示询问次数。接下来 $Q$ 行，每行第一个数为 $k$，而后 $k$ 个正整数 $c_1,c_2,\dots,c_k$ 表示一个大小为 $k$ 的边集，其中 $c_i$ 为边的序号。为了强制在线，每次的 $k$ 与 $c_1,c_2,\dots,c_k$ 均需异或之前回答为连通的个数。 ## Output 对于每个询问输出：连通则为 `Connected`，不连通则为 `Disconnected`（不加引号）。 [samples] ## Note 数据保证，$1\leq n\leq 10^5$，$1\leq m\leq 5\times 10^5$，$1\leq Q\leq 5\times 10^4$，$1\leq k\leq 15$。保证图中没有重边与自环。

Samples

Input #1

Output #1

Connected
Connected
Connected
Connected
Disconnected

API Response (JSON)

{
  "problem": {
    "name": "BZOJ3563 DZY Loves Chinese",
    "description": {
      "content": "给定无向图 $G = (V, E)$，$q$ 次询问每次给定一个边集，求删除该边集后图是否连通。保证边集大小不超过 $15$。强制在线。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10774"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定无向图 $G = (V, E)$，$q$ 次询问每次给定一个边集，求删除该边集后图是否连通。保证边集大小不超过 $15$。强制在线。\n\n## Input\n\n第一行输入两个正整数 $n,m$，表示图的结点数和边数。\n\n接下来 $m$ 行，每行两个正整数 $u_i,v_i$，表示第 $i$ 条边。\n\n接下来输入一行 $Q$，表示询问次数。\n\n接下来 $Q$ 行，每行第一个数为 $k$，而后 $k$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments