小A最多会新认识的多少人

[编程题]小A最多会新认识的多少人

热度指数：6131 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小A参加了一个n人的活动，每个人都有一个唯一编号i(i>=0 & i<n)，其中m对相互认识，在活动中两个人可以通过互相都认识的一个人介绍认识。现在问活动结束后，小A最多会认识多少人？

输入描述:

第一行聚会的人数：n（n>=3 & n<10000）；
第二行小A的编号: ai（ai >= 0 & ai < n)；
第三互相认识的数目: m（m>=1 & m
< n(n-1)/2）；
第4到m+3行为互相认识的对，以','分割的编号。

输出描述:

输出小A最多会新认识的多少人？

示例1

输入

7
5
6
1,0
3,1
4,1
5,3
6,1
6,5

输出

算法知识视频讲解

勇敢牛牛，不怕困难！

// Union_Find_Algorithm

#include <stdio.h>
#include <stdlib.h>

// Path Compression （路径压缩）
int Find(int* p, const int x) {
  return *(p + x) = *(p + x) ^ x ? Find(p, *(p + x)) : x;
}

// Union By Rank (暂不考虑按秩合并)
void Union(int* p, const int u, const int v) {
  *(p + Find(p, u)) = *(p + Find(p, v));
}

int main(const int argc, const char* argv[]) {
  int n, ai, m, i;
  fscanf(stdin, "%d %d %d", &n, &ai, &m);
  
  int p[n];
  for (i = 0; i < n; ++i) *(p + i) = i;
  
  int u, v, count = 1;
  while (m--) {
    fscanf(stdin, "%d,%d", &u, &v);
    if (u == ai || v == ai) ++count;
    Union(p, u, v);  
  }
  
  int cnt = 0, pid = Find(p, ai);
  for (i = 0; i < n; ++i)
    cnt += Find(p, i) == pid;
  
  return printf("%d", cnt - count), 0;
}

#include <vector>

using namespace std;

void depth_first_search_algorithm(vector<vector<int>>& g,
                                  vector<int>& seen,
                                  int cur,
                                  int& ccs) {
  if (seen[cur]++) return;
  
  ++ccs;
  for (int nxt : g[cur])
    depth_first_search_algorithm(g, seen, nxt, ccs);
}

int main(const int argc, const char** argv) {
  int n, ai, m, count = 1;
  cin >> n >> ai >> m;
  
  vector<vector<int>> g(n);
  vector<int> seen(n, 0);
  
  int a, b;
  while (m--) {
    fscanf(stdin, "%d, %d", &a, &b);
    if (a == ai || b == ai) ++count;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  
  int ccs = 0; // connected component size ; // 连通分量的大小
  depth_first_search_algorithm(g, seen, ai, ccs);
  cout << ccs - count;
  return 0;
}

发表于 2021-07-16 08:25:13 回复(0)