小A参加了一个n人的活动,每个人都有一个唯一编号i(i>=0 & i<n),其中m对相互认识,在活动中两个人可以通过互相都认识的一个人介绍认识。现在问活动结束后,小A最多会认识多少人?
小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最多会新认识的多少人?
7 5 6 1,0 3,1 4,1 5,3 6,1 6,5
3
# 方法和之前用Python的那位是一模一样的,只不过写了个并查集的类来实现,我自己是AC了的
class UnionSet:
def __init__(self, n):
self.parents = [i for i in range(n)]
self.rank = [1]*n
def find(self, x):
if self.parents[x] != x:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
if self.rank[px] > self.rank[py]:
self.parents[py] = px
self.rank[px] += self.rank[py]
else:
self.parents[px] = py
self.rank[py] += self.rank[px]
import sys
lines = sys.stdin.readlines()
n = int(lines[0].strip())
A = int(lines[1].strip())
us = UnionSet(n)
seen = set()
for line in lines[3:]:
i, j = list(map(int, line.split(',')))
if i == A:
seen.add(j)
elif j == A:
seen.add(i)
us.union(i, j)
ans = 0
root = us.find(A)
for i in range(n):
if us.find(i) == root:
ans += 1
print(ans - 1 - len(seen)) //顺便复习下并查集,很重要的东东
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
int bianhao = sc.nextInt();
int renshi = sc.nextInt();
ArrayList<Integer> arrList = new ArrayList<Integer>();
for(int i=0;i<n;i++) {
arrList.add(i);
}
UnionFindSet ufs = new UnionFindSet(arrList);
int hasRenshi = 0;
for(int i=0;i<renshi;i++) {
String s = sc.next();
String[] sarr = s.split(",");
String s1 = sarr[0];
String s2 = sarr[1];
Integer i1 = Integer.valueOf(s1);
Integer i2 = Integer.valueOf(s2);
if(i1.equals(bianhao) || i2.equals(bianhao)) {
hasRenshi ++;
}
ufs.union(i1, i2);
}
int size = ufs.sizeMap.get(ufs.findHead(ufs.getElementMap().get(bianhao)));
System.out.println(size - 1 - hasRenshi);
}
}
public static class Element {
public int value;
public Element(int value) {
this.value = value;
}
}
public static class UnionFindSet{
public HashMap<Integer,Element> elementMap;
// key 某个元素 value 该元素的父
public HashMap<Element, Element> fatherMap;
// key 某个集合的代表元素 value 该集合的大小
public HashMap<Element, Integer> sizeMap;
public UnionFindSet(ArrayList<Integer> arrList) {
elementMap = new HashMap<>();
fatherMap = new HashMap<>();
sizeMap = new HashMap<>();
for(Integer item:arrList) {
Element ele = new Element(item);
elementMap.put(item, ele);
fatherMap.put(ele, ele);
sizeMap.put(ele, 1);
}
}
public HashMap<Integer,Element> getElementMap(){
return elementMap;
}
public Element findHead(Element ele) {
Stack<Element> stack = new Stack();
while(ele != fatherMap.get(ele)) {
stack.add(ele);
ele = fatherMap.get(ele);
}
while(!stack.isEmpty()) {
fatherMap.put(stack.pop(), ele);
}
return ele;
}
public boolean isSameSet(Integer a, Integer b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
}
return false;
}
public void union(Integer a, Integer b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
Element aF = findHead(elementMap.get(a));
Element bF = findHead(elementMap.get(b));
if (aF != bF) {
Element big = sizeMap.get(aF) >= sizeMap.get(bF) ? aF : bF;
Element small = big == aF ? bF : aF;
fatherMap.put(small, big);
sizeMap.put(big, sizeMap.get(aF) + sizeMap.get(bF));
sizeMap.remove(small);
}
}
}
}
}
people = int(input())
target = int(input())
t = int(input())
parent = [i for i in range(people)]
rank = [1] * people
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px != py:
if rank[px] >= rank[py]:
rank[px] += rank[py]
parent[py] = px
else:
parent[px] = py
rank[py] += rank[px]
seen = set()
for _ in range(t):
p1, p2 = list(map(int, input().split(',')))
union(p1, p2)
if p1 == target:
seen.add(p2)
elif p2 == target:
seen.add(p1)
if len(seen) == 0:
print(0)
count = 0
root= find(target)
for i in range(people):
if find(i) == root:
count += 1
print(count - 1 - len(seen)) 通过率93.33%,Python运行时间确实久一些,不过这个思路应该没问题
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 8;
vector<int> G[maxn];
int res = 0;
//深度遍历 找到一个集合的人
void dfs(int ai, vector<bool> &v) {
for (int i = 0; i < G[ai].size(); ++i) {
if (!v[G[ai][i]]) {
v[G[ai][i]] = true;
res++;
dfs(G[ai][i], v);
}
}
return;
}
int main() {
int n, ai, m;
cin >> n >> ai >> m;
//构建邻接表
while (m--) {
int p1, p2;
char chs;
cin >> p1 >> chs >> p2;
G[p1].push_back(p2);
G[p2].push_back(p1);
}
vector<bool> visited(n, false);
//除去本来就认识的人和自己
int already = G[ai].size() + 1;
dfs(ai,visited);
cout << res - already << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int p[10001];
int findParent(int x){
return (p[x]==x)?x:p[x]=findParent(p[x]);
}
int main(){
int n,m,t,cnt=0;
cin>>n>>t>>m;
for(int i=0;i<n;i++)
p[i] = i;
for(int i=0;i<m;i++){
int a,b;
scanf("%d,%d", &a, &b);
int pa = findParent(a);
int pb = findParent(b);
if(a==t || b==t)
cnt--;
if(pa != pb)
p[pa] = pb;
}
for(int i=0;i<n;i++)
if(findParent(i) == findParent(t))
cnt++;
cout<<cnt-1<<endl;
return 0;
} //并查集基本应用,最后别忘了减掉本身
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,ix,m;
vector<int>f;
int find(int x){
return x==f[x]?x:f[x]=find(f[x]);
}
int main(void){
cin>>n>>ix>>m;
f=vector<int>(n);
for(int i=0;i<n;i++)f[i]=i;
int ans=0,b=0;
while(m--){
int one,two;
scanf("%d,%d",&one,&two);
if(one==ix||two==ix)b++;
int fx=find(one),fy=find(two);
if(fx!=fy)f[fx]=fy;
}
for(int i=0;i<n;i++){
if(find(ix)==find(i))ans++;
}
cout<<ans-b-1<<endl;
return 0;
}
import java.util.*;
// BFS: 认识是双向的, 从A点出发BFS (初始queue、set要注意)
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int ai = in.nextInt();
List<List<Integer>> list = new ArrayList<>(); // 邻接表
for (int i = 0; i < n; i++) list.add(new ArrayList<>());
int m = in.nextInt();
while (m-- > 0) {
String[] sp = in.next().split(",");
int u = Integer.parseInt(sp[0]);
int v = Integer.parseInt(sp[1]);
list.get(u).add(v);
list.get(v).add(u);
}
Queue<Integer> queue = new LinkedList<>();
queue.offer(ai);
for (int v : list.get(ai)) queue.offer(v); //初始A及认识的人
Set<Integer> set = new HashSet<>(list.get(ai));
set.add(ai); // A自己也加上
int start = set.size(); // A初始认识的人
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : list.get(u)) {
if (set.contains(v)) continue; // 已访问,去重
set.add(v);
queue.offer(v);
}
}
System.out.print(set.size() - start);
}
} #include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <iterator>
#include <set>
using namespace std;
int main() {
int n;
int i;
int m;
cin >> n;
cin >> i;
cin >> m;
map<int,set<int>> nn;
map<int,bool> visited;
for(int j=0;j<m;j++){
int a,b;
char c;
cin >> a >> c >> b;
nn[a].insert(b);
nn[b].insert(a);
visited[a] = false;
visited[b] = false;
}
// BFS
set<int> to_visit = nn[i];
visited[i] = true;
int num = 0;
while(true){
set<int> to_visit_add = {};
for(auto e:to_visit){
if(visited[e]) continue;
visited[e] = true;num++;
to_visit_add.insert(nn[e].begin(), nn[e].end());
}
if(to_visit_add.empty()) break;
to_visit = to_visit_add;
}
cout<<num-nn[i].size();
}
//广度优先搜索,最后一个列子没通过,时间不够了
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n;
cin >> n;
int numiofA;
cin >> numiofA;
int m;
cin >> m;
vector<pair<int, int>> friends;
int no1, no2;
char ch;
while (cin >> no1 >> ch >> no2) {
friends.emplace_back(no1, no2);
}
int ans=0;
queue<int>q;
vector<int>arr(n);
for (int i = 0; i < m; i++) {
if (friends[i].first == numiofA) {
q.push(friends[i].second);
arr[friends[i].second] = 2;//本来就认识,ans不++
}
if (friends[i].second == numiofA) {
q.push(friends[i].first);
arr[friends[i].first] = 2;
}
}
arr[numiofA] = 2;
while (!q.empty()) {
auto x = q.front();
q.pop();
int nn=friends.size();
for (int i = 0; i < nn; i++) {
if (friends[i].first == x && arr[friends[i].second] == 0) {
q.push(friends[i].second);
arr[friends[i].second] = 1;
ans++;
}
if (friends[i].second == x && arr[friends[i].first] == 0) {
q.push(friends[i].first);
arr[friends[i].first] = 1;
ans++;
}
}
}
cout<<ans;
return 0;
} #include <bits/stdc++.h>
using namespace std;
pair<int, int> splitStr(const string &str) {
string::size_type pos = str.find(",");
string str1 = str.substr(0, pos), str2 = str.substr(pos+1);
int num1 = stoi(str1); // 从 pos 开始到结束的字符串
int num2 = stoi(str2);
return {num1, num2};
}
map<int, int> BFS (int &p, vector<vector<int>> &link) {
// 广度优先搜索
queue<int> linkQue; linkQue.push(p);
map<int, int> linkMap;
while (!linkQue.empty()) {
int cur = linkQue.front(); linkQue.pop();
linkMap[cur]++;
for (auto &nxt : link[cur]) {
if ( !linkMap[nxt] ) // 不重复出现关系网
linkQue.push(nxt); // 将 cur 的朋友 nxt 放到队列中
}
}
return linkMap;
}
int main() {
int n; cin >> n; // 参加聚会人数
vector<vector<int>> link(n);
int aNum; cin >> aNum; // a的编号
int m; cin >> m; // 互相认识的个数
while(m--){
string str; cin >> str;
int p1 = splitStr(str).first, p2 = splitStr(str).second;
link[p1].push_back(p2); // 互相认识的人
link[p2].push_back(p1);
}
cout << BFS(aNum, link).size() - link[aNum].size() - 1;
return 0;
} class DSU:
def __init__(self,n: int):
self.p = [i for i in range(n)]
self.cnt = [1] * n
def find(self,x: int) -> int:
if x != self.p[x]: self.p[x] = self.find(self.p[x])
return self.p[x]
def merge(self,x: int,y: int):
rx , ry = self.find(x) , self.find(y)
if rx == ry: return
self.p[rx] = ry
self.cnt[ry] += self.cnt[rx]
return
def main():
n = int(input())
dsu = DSU(n)
p = int(input())
m = int(input())
res = 0
for _ in range(m):
a ,b = map(int,input().split(','))
if a == p:
res -= 1
if b == p:
res -= 1
dsu.merge(a,b)
fa = dsu.find(p)
print(dsu.cnt[fa] + res - 1)
if __name__ == '__main__':
main()
并查集模版题
图的数据结构必须邻接矩阵,简直裂开!
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(reader.readLine());
int ai = Integer.parseInt(reader.readLine());
int m = Integer.parseInt(reader.readLine());
int[][] pairs = new int[m][2];
for (int i = 0; i < m; i++) {
String[] D = reader.readLine().split(",");
pairs[i][0] = Integer.parseInt(D[0]);
pairs[i][1] = Integer.parseInt(D[1]);
}
Map<Integer, ArrayList<Integer>> A = new HashMap<>();
for (int[] pair : pairs) {
if (!A.containsKey(pair[0])) {
A.put(pair[0], new ArrayList<>());
}
if (!A.containsKey(pair[1])) {
A.put(pair[1], new ArrayList<>());
}
A.get(pair[0]).add(pair[1]);
A.get(pair[1]).add(pair[0]);
}
Queue<Integer> queue = new LinkedList<>();
Set<Integer> hasVisited = new HashSet<>();
queue.add(ai);
int res = 0;
while (!queue.isEmpty()) {
int idx = queue.poll();
if (hasVisited.contains(idx)) {
continue;
}
if (A.get(idx) != null) {
for (int num : A.get(idx)) {
queue.add(num);
}
}
hasVisited.add(idx);
res++;
}
if (A.get(ai) != null) {
res -= A.get(ai).size();
}
res-=1;
writer.write(String.valueOf(res));
reader.close();
writer.close();
}
}
//并查集求联通块内的点数量,但是要减去时间相连的,用hashset存一下就好了
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
public class Main {
static int N = 10010, n, start, m;
static int[] p = new int[N], cnt = new int[N];
static int find(int x){
if(p[x] != x)
p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt(); start = in.nextInt(); m = in.nextInt();
for(int i = 0; i < n; i ++) p[i] = i;
HashSet<Integer> set = new HashSet<>();
Arrays.fill(cnt, 1);
for(int i = 1; i <= m; i ++){
String[] arr = in.next().split(",");
int a = Integer.parseInt(arr[0]), b = Integer.parseInt(arr[1]);
if(a == start || b == start){
set.add(a); set.add(b);
}
int pa = find(a), pb = find(b);
if(pa != pb){
p[pa] = pb;
cnt[pb] += cnt[pa];
}
}
System.out.println( cnt[find(start)] - set.size());
}
}
// 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;
} class Node(object):
def __init__(self, v):
self.v = v
self.neighbors = []
def solve(graph, target):
counter = 0
n = len(graph)
visited = [False for _ in range(n)]
stack = [target]
visited[target] = True
while stack:
v = stack.pop()
for i in graph[v].neighbors:
if not visited[i]:
visited[i] = True
counter += 1
stack.append(i)
return counter
while True:
try:
num_person = int(input().strip())
target = int(input().strip())
graph = [Node(i) for i in range(num_person)]
num_edge = int(input().strip())
for _ in range(num_edge):
li = input().strip().split(',')
i, j = [int(_) for _ in li]
graph[i].neighbors.append(j)
graph[j].neighbors.append(i)
ans = 0
nei_num = len(graph[target].neighbors)
if nei_num:
ans = solve(graph, target) - nei_num
print(ans)
except Exception as e:
#print(e)
break
import java.util.HashSet;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
UF uf = new UF(Integer.parseInt(scanner.nextLine()));
int a = Integer.parseInt(scanner.nextLine());
int m = Integer.parseInt(scanner.nextLine());
int b = 0;
int ans = 0;
HashSet<Integer> set = new HashSet<>();
while (m > 0){
String[] str = scanner.nextLine().split(",");
int i = Integer.parseInt(str[0]);
int j = Integer.parseInt(str[1]);
if(i == a || j == a) b++;
set.add(i);
set.add(j);
uf.union(i,j);
m--;
}
for (Integer integer : set) {
if(uf.connected(a,integer)) ans++;
}
System.out.println(ans - b - 1);
}
}
class UF {
private int[] parent;
private int[] size;
public UF(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
// 小树接到大树下面,较平衡
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
} else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
}
public boolean connected(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}
private int find(int x) {
while (parent[x] != x) {
// 进行路径压缩
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}
祖传的并查集类,再根据题意稍微改改就好,这个题别忘了减去自身问题就不大