PAT学到了 2019/9/1

【本质是看别人的代码学东西】

1.邻接矩阵访问图所需数据结构

int edge[][];

int visited[];

 其中 visited 需要初始化全部为0，一种相对简单的方式是使用 #include<memory.h>/<string.h> 的 memset函数：

memset(visited,0,sizeof(visited));

2.邻接矩阵访问图的两种基本方法

DFS:

void dfs( int v ) {
	visited[v] = 1;
	for (int i = 1; i <= N; i++) {
		if (!visited[i] && edge[i][v] == 1)
			dfs(i);
	}
}

BFS:

void bfs(int v) {
	queue<int> q;
	q.push(v);
	visited[v] = 1;
	while (!q.empty()) {
		int n = q.front();
		q.pop();
		for (int i = 1; i <= N; i++) {
			if (!visited[i] && edge[n][i] == 1) {
				q.push(i);
				visited[i] = true;
			}
		}
	}
}

3.cin和cout的性能很差，摘：

cout和cin的设计，可能比我们想象的复杂的多，从实际测试的结果，速度比printf和scanf慢一个数量级以上。影响cout和cin的性能的有两个方面：同步性和缓冲区，同步性可以通过ios_base::sync_with_stdio(false)禁用；操作系统会对缓冲区进行管理和优化，但十分有限，使用了endl之后，会对缓冲区执行清空操作，这个过程会先执行’\n’，再执行flush操作，非常漫长，所以尽量使用‘\n’而不是endl执行换行。然后，还有一个cout和cin的绑定效果，两者同时使用的话，cin与cout交替操作，会有一个flush过程，所以还是会很漫长，可以通过cin.tie(0)禁用绑定。
————————————————
版权声明：本文为CSDN博主「CodeLike」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/cv_jason/article/details/81019874

 4.并查集两个核心算法

Find（查找根节点）

int father[];

for( int i = 0 ; i < father.size() ; i ++ ){
	father[i] = i;
}

int findFather(int child) {
	if (child == father[child])
		return child;
	return father[child] = findFather(father[child]);
}

union/merge（压缩路径）

void merge(int u, int v) {
	int fu = find(u);
	int fv = find(v);
	if (fu != fv) {
		father[fu] = fv;
	}
}

5.科学计数法: 1e5 = 1*10⁵

6.注意双等号！！