Codeforces Beta Round #25 D 题 Roads not only in Berland

发表于 分类于

这题算是数据结构类型的题目了吧，运用并查集可以快速地解决此类问题，从头往后读取数据，如果读取到的两个点不在同一个集合里，就将他们合并，否则，这条边就是多余的，将多余的边放入栈 stst 中。处理完边之后，线性扫一遍结点数组，找出所有的根结点放入栈 donedone 中。

之后从 stst 中取出一元素，将 donedone 中的两个元素连起来，然后任意去掉一个元素，留下一个元素，不断进行，直到栈 stst 空了为止结束循环。

这个过程主要是运用好栈和并查集。。

第一题和第二题比较简单，就不在此多说，剩下的题目尝试写了下，没有写出。

我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;
const int MAX = 1100;
struct Node {
  int x;
  int y;
} st[MAX];
int p[MAX], rank[MAX], top = 0, done[MAX], dtop = 0;
int n;

void init() {
  for (int i = 1; i <= n; i++) {
    p[i] = i;
    rank[i] = 0;
  }
}

int Find(int x) {
  if (p[x] != x) p[x] = Find(p[x]);
  return p[x];
}

void Link(int x, int y) {
  if (rank[x] < rank[y]) {
    p[x] = y;
  } else {
    p[y] = x;
    if (rank[x] == rank[y]) rank[x]++;
  }
}

void Union(int x, int y) { Link(Find(x), Find(y)); }

int main() {
  int x, y;
  scanf("%d", &n);
  init();
  for (int i = 0; i < n - 1; i++) {
    scanf("%d%d", &x, &y);
    if (Find(x) != Find(y)) {
      Union(x, y);
    } else {
      st[top].x = x;
      st[top].y = y;
      top++;
    }
  }
  for (int i = 1; i <= n; i++) {
    if (Find(i) == i) {
      done[dtop] = i;
      dtop++;
    }
  }
  printf("%d\n", top);
  while (top) {
    x = done[dtop - 1];
    y = done[dtop - 2];
    dtop--;
    top--;
    printf("%d %d %d %d\n", st[top].x, st[top].y, x, y);
  }
  return 0;
}