STL及常用算法

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    bool operator < (const node &b)const{ //重载运算符
        return data < b.data;
    }
};
int main()
{
    //队列
    queue<int>qu;
    queue<node>qu;
    //优先队列
    priority_queue<int>qu; //从大到小
    priority_queue<int, vector<int>, greater<int> >qu; //从小到大
    priority_queue<node>qu; //结构体
    qu.push({1});
    qu.push({2});
    cout << qu.top().data << endl;
    //集合
    set<int>st;
    st.insert(1);
    set<int>::iterator it;
    it = st.lower_bound(1);
    st.insert(st.begin(), st.end());
    //映射
    map<int,int>mp;
    map<int,int>::iterator it;
    mp[1] = 2;
    it = mp.lower_bound(1);
    cout << it->second << endl;

}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10010;
int pre[maxn];
int fin(int x){return x == pre[x] ? x : pre[x] = fin(pre[x]);}
int main()
{
    int n = maxn;
    for(int i = 0; i <= n; i++)pre[i] = i;
    int x = fin(1);
    int y = fin(2);
    if(x != y)pre[x] = y;
}

1	#include <bits/stdc++.h>
2	using namespace std;
3	const int maxn = 10010;
4	vector<int>mp[maxn];
5	int n, vis[maxn] = {0};
6	void dfs(int x)
7	{
8	vis[x] = 1;
9	for(int i = 0; i < mp[x].size(); i++)
10	{
11	int v = mp[x][i];
12	if(vis[v] == 0)
13	{
14	dfs(v);
15	}
16	}
17	vis[x] = 0;
18	}
19	void bfs(int x)
20	{
21	queue<int>qu;
22	qu.push(x);
23	vis[x] = 1;
24	while(!qu.empty())
25	{
26	int w = qu.front();
27	qu.pop();
28	for(int i = 0; i < mp[w].size(); i++)
29	{
30	int v = mp[w][i];
31	if(vis[v] == 0)
32	{
33	qu.push(v);
34	vis[v] = 1;
35	}
36	}
37	}
38	}

1	int main()
2	{
3	mp[1].push_back(2);
4	mp[2].push_back(1);
5	dfs(1);
6	bfs(1);
7	}
8
9	#include <bits/stdc++.h>
10	#define inf 0x3f3f3f
11	using namespace std;
12	const int maxn = 1010;
13	int mp[maxn][maxn] = {0};
14	int n = 3, st = 1, ed = 3;
15	void dij()
16	{
17	int dis[maxn], vis[maxn] = {0};
18	for(int i = 0; i <= n; i++)dis[i] = inf;
19	vis[st] = 1;
20	dis[st] = 0;
21	for(int i = 0; i < n; i++)
22	{
23	int u = -1, minn = inf;
24	for(int j = 1; j <= n; j++)
25	{
26	if(dis[j] < minn)
27	{
28	minn = dis[j];
29	u = j;
30	}
31	}
32	if(u > 0)vis[u] = 1;
33	else continue;
34	for(int j = 1; j <= n; j++)
35	{
36	if(vis[j] == 0 && dis[j] > dis[u] + mp[u][j])
37	{
38	dis[j] = dis[u] + mp[u][j];
39	}
40	}
41	}
42	}
43	void floyd()
44	{
45	int i, j, k;
46	for(k = 1; k <= n; k++)
47	{
48	for(i = 1; i <= n; i++)
49	{
50	for(j = 1; j <= n; j++)
51	{
52	if(mp[i][j] > mp[i][k] + mp[k][j])
53	{
54	mp[i][j] = mp[i][k] + mp[k][j];
55	}
56	}
57	}
58	}
59	}
60	int spfa()
61	{
62	int vis[maxn] = {0}, dis[maxn], cnt[maxn] = {0};
63	for(int i = 1; i <= n; i++)dis[i] = inf;
64	dis[st] = 0;
65	queue<int>qu;
66	qu.push(st);
67	vis[st] = 1;
68	cnt[st]++;
69	while(!qu.empty())
70	{
71	int w = qu.front();
72	qu.pop();
73	for(int i = 1; i <= n; i++)
74	{
75	if(vis[i] == 0 && dis[i] > dis[w] + mp[w][i])
76	{
77	dis[i] = dis[w] + mp[w][i];
78	vis[i] = 1;
79	qu.push(i);
80	cnt[i]++;
81	}
82	}
83	vis[w] = 0;
84	}
85	return dis[ed];
86	}
87	int main()
88	{
89	mp[1][2] = mp[2][1] = 1;
90	mp[1][3] = mp[3][1] = 2;
91	mp[2][3] = mp[3][2] = 4;
92	cout << spfa();
93	}

STL

并查集

搜索 DFS && BFS

最短路 Dijstra && Floyd && SPFA

1	#include <bits/stdc++.h>
2	using namespace std;
3	struct node
4	{
5	int data;
6	bool operator < (const node &b)const{ //重载运算符
7	return data < b.data;
8	}
9	};
10	int main()
11	{
12	//队列
13	queue<int>qu;
14	queue<node>qu;
15	//优先队列
16	priority_queue<int>qu; //从大到小
17	priority_queue<int, vector<int>, greater<int> >qu; //从小到大
18	priority_queue<node>qu; //结构体
19	qu.push({1});
20	qu.push({2});
21	cout << qu.top().data << endl;
22	//集合
23	set<int>st;
24	st.insert(1);
25	set<int>::iterator it;
26	it = st.lower_bound(1);
27	st.insert(st.begin(), st.end());
28	//映射
29	map<int,int>mp;
30	map<int,int>::iterator it;
31	mp[1] = 2;
32	it = mp.lower_bound(1);
33	cout << it->second << endl;
34
35	}