地铁打卡活动

第一次碰到这种题，楼上的代码非常简洁，初学者很难看懂。
然后我去搜了下关键字“并查集”，
嘿嘿。代码和楼上的一样，只是加一些注释而已，方便初学者。
#include <iostream>
using namespace std;
const int N = 1e5 + 50;
int n, m, a, b, u, v;
int parent[N];
//寻找根节点的函数，并作路径压缩
/*如果节点x和他的父节点相同，则x就是根节点，直接返回；
否则，继续寻找x父节点的父节点，直到找到
根节点后返回，并将节点x的父节点改为根节点。*/
int find(int x) {
    return x == parent[x] ? x : parent[x] = find(parent[x]);
}
//合并两个节点，把其中一个节点的父亲换成另一个节点
void to_union(int i, int j) {
	parent[find(i)] = find(j);
}
int main()
{
	cin >> n >> m >> a >> b;
        //初始化：所有节点的父节点都是自己，即自身就是根节点
	for (int i = 0; i<n; i++) {
		parent[i] = i;
	}
        //合并两个节点
	for (int i = 1; i <= m; i++) {
		cin >> u >> v;
		to_union(u, v);
	}
	int cnt = 0;
        //寻找根节点个数
	for (int i = 0; i<n; i++) {
		if (parent[i] == i) {
			cnt++;
		}
	}
        //计算票价
	int ans = b + b + (cnt - 1)*b + cnt*a;
	printf("%d\n", ans);
	return 0;
}

#include <iostream>
using namespace std;

//用来存储每个点的父节点（这里1000我随意取的）
int t[1000];

int find(int x) {
    //比较low一点的寻找父节点方法（其实就是路径压缩不彻底）
   /* while(x != t[x]){
        t[x] = find(t[x]);
        x = t[x];
    }
    return x;*/
    if(x == t[x])return x;  //说明当前的节点就是根节点
    else {
        //这边的递归就是进行路径的压缩（就是相当于每个节点最终的父节点都是 同一个（连通的））
        t[x] = find(t[x]);
        return t[x];
    }
}

void untion(int t1, int t2) {
    int x1 = find(t1);
    int x2 = find(t2);

    //这个题有缺陷，其原则上不管输入的两个节点是不是已经是同一个父节点，都要将其相连通，所以不用进行父节点的判断（但一般并查集还是需要判断的，这个题判断也不会出错）
    /*if (x1 != x2) {
        t[x1] = x2;
    }*/
    //直接将t1所在的树挂到t2上面去,也就是偷偷的替换掉t1的所在的父节点的父节点
    t[x1] = x2;
}

int main() {
    //其中n表示地铁站点数，m表示连通的地铁站点对数，a代表地铁最低票价，b代表非地铁方式票价，其中0 < a < b
    int m, n;  
    float a, b;
    int t1, t2; //临时记录哪两个节点需要连通
    int i, j;
    int count = 0;//用来记录根节点的个数
    int res = 0; //用来记录最终的票价 
    cin >> n >> m >> a >> b;

    for ( i = 0; i < n; i++) {
        //初始化每个站点的都是一个孤立的点（就是父节点仍是本身）
        t[i] = i;
    }

    for (j = 0; j < m; j++) {
        //将后面的m行 两两孤立点 连通起来
        cin >> t1 >> t2;
        untion(t1, t2);
    }

    for (i = 0; i < n; i++) {
        if (i == find(i)) {
            //说明该节点是根节点(因为相当于其父节点就是自身)
            count++;
        }
    }
    //a*count 因为节点所属同一个根节点只需要花费a元，b*2指的是最开始酒店去其中一个节点花费b元，最后从某个节点回酒店花费b元
    //b*(count-1) 因为不同根节点之间需要花费 b元，那么count个根节点，则必有count-1个不连通的根节点
    res = a*count + b * 2 + b*(count - 1);
    cout << res << endl;
    return 0;
}

class Graph():
    def __init__(self,nodes,sides):
        '''
        nodes 表示点, list
        sides 表示边(两个点组成的边), a list of tuple
        '''
        # self.sequence是字典，key是node，value是与key相连接的点(是list)
        self.sequence = {}
         # self.side是临时变量，主要用于保存与指定点相连接的点
        self.side=[]
        for node in nodes:
            for side_tuple in sides:  ## side_tuple is a tuple
                u,v=side_tuple
                (2165)# 指定点与另一个点在同一个边中，则说明这个点与指定点是相连接的点，则需要将这个点放到self.side中
                if node == u:
                    self.side.append(v)
                elif node == v:
                    self.side.append(u)
            self.sequence[node] = self.side
            self.side=[]

    def DFS(self, node0):
        # queue本质上是栈，用来存放需要进行遍历的数据
        (2166)# order里面存放的是具体的访问路径
        queue, order = [], []
        # 首先将初始遍历的节点放到queue中，表示将要从这个点开始遍历
        queue.append(node0)
        while queue:
            (2167)# 从queue中pop出点v，然后从v点开始遍历了，所以可以将这个点pop出，然后将其放入order中
            # 这里才是最有用的地方，pop()表示弹出栈顶，由于下面的for循环不断的访问子节点，并将子节点压入堆栈，
            (2168)# 也就保证了每次的栈顶弹出的顺序是下面的节点
            v = queue.pop()  #####LIFO
            order.append(v)
            (2169)# 这里开始遍历v的子节点
            for w in self.sequence[v]:  #####
                (750)# w既不属于queue也不属于order，意味着这个点没被访问过，所以将其放到queue中，然后后续进行访问
                if w not in order and w not in queue:
                    queue.append(w)
        return order

if __name__ == "__main__":
    n,m,a,b = map(int,input().strip().split())
    nodes = [i for i in range(n)]
     sides=[]
    for i in range(m):
        t= set(map(int,input().strip().split()))
        sides.append(t)

     g=Graph(nodes,sides)
     side_list=[]
    side_list_all=[]
    for node in nodes:
       side_list=g.DFS(node)  
       side_list_all.append(tuple(sorted(side_list)))

     cnt=1
    dict_con={}
    for i in range(len(side_list_all)-1):
        if(side_list_all[i] not in dict_con):
            dict_con.update({side_list_all[i]:1})
        else:
            dict_con[side_list_all[i]]+=1
    cnt=len(dict_con.keys())
     cost = 2 * b + b * (cnt-1) + a * cnt
    print(cost)

这道题是求无向图的最大连通分量，定义图后，用深搜找出每个点的连通节点，再统计不同的连通分量的个数。