列表

详情

NC14363. Graph Generator

描述

DreamGrid has made a graph generator. The generator will take in a single integer n and generate an undirected graph with n vertices.

More specifically, the generator will generate an empty graph G and a permutation p of  {1, 2, ..., n} . After that, the generator will do the following operations n times and during the q-th operation:

  1. 1.Find the all connected components C1, C2, ..., Cm in G.
  2. 2.Choose a subset Sq of   such that no two vertices in Sq belong to the same connected component.
  3. 3.Create a new vertex with index pq in G and add an edge between pq and every vertex v in , where beli is the index of connected component which i belongs to.

Given the final generated graph, DreamGrid would like to know all the pq and Sq.

输入描述

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers n and m (1 ≤ n ≤ 105, 0 ≤ m ≤ min(105, ) -- the number of vertices and the number of edges.
Each of the next m lines contains two integers ui and vi (1 ≤ ui, vi ≤ n). There will be no self loops or multiple edges.
It is guaranteed that neither the sum of all n nor the sum of all m exceeds 2 *106.

输出描述

For each test case, if the the graph cannot be generated by the generator, output "No" in the first line. Otherwise, output "Yes" in the first line. Then in the i-th of the following line, output two integers pi and si (1 ≤ pi ≤ n) followed with si integers: a1, a2, ..., asi (1 ≤ aj ≤ n) -- the index of the newly created vertex and the subset during the i-th operation. If there are multiple solutions, print any of them.

示例1

输入: 

3
3 0
4 4
1 2
2 3
3 4
2 4
5 5
1 2
2 3
3 4
4 5
2 4

输出: 

Yes
1 0
2 0
3 0
Yes
1 0
4 0
3 1 4
2 2 1 3
No

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 423ms, 内存消耗: 16504K, 提交时间: 2019-01-08 11:55:29 

#include <cstdio>
#include <vector>

const int N = 1e5 + 10;

std::vector<int> tree[N];
std::vector<int> adj[N];
int deg[N], ind[N], anc[N], size[N];

bool dfs(int u) {
  size[u] = 1;
  for (auto &&v: tree[u]) {
    anc[v] = anc[u] + 1;
    if (!dfs(v)) return false;
    size[u] += size[v];
  }
  return deg[u] == anc[u] + size[u] - 1;
}

void generate(int u) {
  for (auto &&v: tree[u]) {
    generate(v);
  }
  printf("%d %d", u + 1, (int)tree[u].size());
  for (auto &&v: tree[u]) {
    printf(" %d", v + 1);
  }
  puts("");
}

int main() {
  int T;
  scanf("%d", &T);
  for (int cas = 1; cas <= T; ++cas) {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
      deg[i] = ind[i] = anc[i] = 0;
      tree[i].clear();
      adj[i].clear();
    }
    std::vector<std::pair<int, int>> edges(m);
    for (int i = 0; i < m; ++i) {
      int u, v;
      scanf("%d%d", &u, &v);
      --u, --v;
      edges[i] = {u, v};
      adj[u].push_back(v);
      adj[v].push_back(u);
      deg[u]++, deg[v]++;
    }
    for (auto &&e: edges) {
      int u = e.first, v = e.second;
      if (deg[u] > deg[v] || (deg[u] == deg[v] && u < v)) ++ind[v];
      else ++ind[u];
    }
    for (int v = 0; v < n; ++v) {
      if (!ind[v]) continue;
      int u = -1;
      for (auto &&i: adj[v]) if (deg[i] > deg[v] || (deg[i] == deg[v] && i < v)) {
        if (u == -1 || ind[u] < ind[i]) u = i;
      }
      tree[u].push_back(v);
    }
    bool valid = true;
    for (int i = 0; i < n && valid; ++i) {
      if (!ind[i]) valid &= dfs(i);
    }
    if (!valid) puts("No");
    else {
      puts("Yes");
      for (int i = 0; i < n; ++i) {
        if (!ind[i]) generate(i);
      }
    }
  }
  return 0;
}

上一题

© 2024 nowcoder.com