图

tpsort O(n + m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
struct tpsort{
	int n;
	vector<vector<int>>e;
	vector<int>ru;
	vector<int>ans;

	tpsort(int n){
		this -> n = n;
		ans.clear();
		e.resize(n+2);
		ru.assign(n+2, 0);
		for(int i = 1; i <= n; i++)e[i].clear();
	}

	void tp(){
		queue<int>q;
		for(int i = 1; i <= n; i++)if(!ru[i])q.push(i);
		while(!q.empty()){
			auto u = q.front(); q.pop();
			ans.push_back(u);
			for(auto v : e[u]){
				if(!(--ru[v]))q.push(v);
			}
		}
	}

};

ll n, m;

void solve(){
	cin >> n;
	tpsort tp(n);
	for(int v, u = 1; u <= n; u++){
		cin >> v;
		tp.e[u].push_back(v);
		tp.ru[v]++;
	}

	tp.tp();

	cout << n - tp.ans.size() << '\n';
	return ;

}

tpsort用于解决有次序的问题，即先完成a才能完成b，
同时tpsort用于解决图，树的dp问题
tp序是不唯一的，当题目有特殊要求的时候，queue用priority_queue代替

dijkstra O(n _ n, (n + m) _ logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
struct Dij{
	int n;
	vector<vector<pll>>e;
	vector<ll>dis;
	vector<bool>vis;

	Dij(int n){
		this -> n = n;
		e.resize(n+2);
		dis.assign(n+2, INF);
		vis.assign(n+2, 0);
		for(int i = 1; i <= n; i++)e[i].clear();
	}

	void di(int s){
		priority_queue<pll, vector<pll>, greater<pll>>q;
		dis[s] = 0;
		q.push(pll{0, s});
		while(!q.empty()){
			auto it = q.top(); q.pop();
			int u = it.second;
			if(vis[u])continue;
			vis[u] = 1;
			for(auto [v, w] : e[u]){
				if(dis[v] > dis[u] + w){
					dis[v] = dis[u] + w;
					q.push(pll{dis[v], v});
				}
			}
		}
	}
};

ll n, m, s;

void solve(){
	cin >> n >> m >> s;
	Dij di(n);
	for(int i = 1; i <= m; i++){
		int u, v, w; cin >> u >> v >> w;
		di.e[u].push_back(pll{v, w});
		//di.e[v].push_back(pll{u, w});
	}
	di.di(1);
	for(int i = 1; i <= n; i++){
		cout << di.dis[i] << " \n"[i==n];
	}
	return ;

}

spfa O(m, m * n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
struct Spfa{
	int n;
	vector<vector<pll>>e;
	vector<ll>dis;
	vector<int>sum;
	vector<bool>vis;

	Spfa(int n){
		this -> n = n;
		e.resize(n+5);
		dis.assign(n+5, INF);
		sum.assign(n+5, 0);
		vis.assign(n+5, 0);
		for(int i = 1; i <= n; i++)e[i].clear();
	}

	bool spfa(int s){
		queue<int>q;
		dis[s] = 0; vis[s] = 1; sum[s] = 1;
		q.push(s);
		while(!q.empty()){
			int u = q.front(); q.pop();
			vis[u] = 0;
			for(auto [v, w] : e[u]){
				if(dis[v] > dis[u] + w){
					dis[v] = dis[u] + w;
					if(!vis[v]){
						q.push(v);
						vis[v] = 1;
						sum[v]++;
						if(sum[v] > n)return 0;
					}
				}
			}
		}
		return 1;
	}

};

ll n, m;

void solve(){
	cin >> n >> m;
	Spfa sp(n);
	for(int i = 1; i <= m; i++){
		int u, v, w; cin >> u >> v >> w;
		sp.e[u].push_back(pll{v, w});
		if(w >= 0)sp.e[v].push_back(pll{u, w});
	}

	if(sp.spfa(1))cout << "NO" << '\n';
	else cout << "YES" << '\n';
	return ;
}

floyd O(n * n *n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
用一句话概括就是：从i号顶点到j号顶点只经过前k号点的最短路程
struct Floyd{
	int n;
	vector<vector<bool>>e;

	Floyd(int n){
		this -> n = n;
		e.assign(n+5, vector<bool>(n+5, 0));
	}

	void floyd(){
		for(int k = 1; k <= n; k++){
			for(int i = 1; i <= n; i++){
				for(int j = 1; j <= n; j++){
					//e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
					e[i][j] = (e[i][j] | (e[i][k] & e[k][j]));
				}
			}
		}
	}
};

ll n, m;

void solve(){
	cin >> n >> m;
	Floyd fl(n);
	for(int i = 1; i <= m; i++){
		int u, v; cin >> u >> v;
		fl.e[u][v] = 1;
	}
	int ans = 0;
	fl.floyd();
	for(int i = 1; i <= n; i++){
		int cnt = 1;
		for(int j = 1; j <= n; j++){
			if(i == j)continue;
			cnt = cnt & (fl.e[i][j] | fl.e[j][i]);
		}
		ans += cnt;
	}
	cout << ans << '\n';

}

Kruskal O(m * logm)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
struct DSU{
	int n;
	vector<int>fa, sz;

	DSU(int n){
		init(n);
	}

	void init(int n){
		this -> n = n;
		fa.assign(n + 5, 0);
		sz.assign(n + 5, 1);
		for(int i = 0; i <= n; i++)fa[i] = i;
	}

	int find(int k){
		return k == fa[k] ? k : fa[k] = find(fa[k]);
	}

	bool same(int u, int v){
		return find(u) == find(v);
	}

	void un(int u, int v){
		u = find(u); v = find(v);
		if(u == v)return ;
		sz[u] += sz[v];
		fa[v] = u;
	}


	int size(int x){
		return sz[find(x)];
	}

};
ll n, m, k;
array<int, 3>e[N];

void solve(){
	cin >> n >> m >> k;
	DSU d(n);
	for(int i = 1; i <= m; i++){
		cin >> e[i][1] >> e[i][2] >> e[i][0];
	}
	sort(e + 1, e + 1 + m);
	ll c = n;
	for(int i = 1; i <= m; i++){
		if(c == 1)break;
		u = e[i][1]; v = e[i][2]; w = e[i][0];
		u = d.find(u); v = d.find(v);
		if(!d.same(u, v)){
			if(d.size(u) > d.size(v))swap(u, v);
			d.un(u, v);
			c--;
		}
	}
    if(c > 1)cout << "NO" << '\n';
    else cout << "YES" << '\n';
    return ;
}

图匹配

二分图染色

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int n, m, a[N], color[N];
vector<int>e[N];

void solve(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		e[i].clear();
	}
	int u, v;
	for(int i = 1; i <= m; i++){
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}

	auto dfs =[&] (auto& dfs, int u, int c) -> bool{
		color[u] = c;
		for(int v : e[u]){
			if(!color[v]){
				if(!dfs(dfs, v, 3 - c))return false;
			}
			else if(color[v] == c)return false;
		}
		return true;
	};

	for(int i = 1; i <= n; i++)if(!color[i])if(!dfs(dfs, i, 1)){
		cout << "NO" << '\n';
		return;
	}
	for(int i = 1; i <= n; i++)cout << i << ' ' << color[i] << '\n';
	cout << "YES" << '\n';
	return ;

}

二分图最大匹配

1
2


二分图最大权匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
struct KM{
	int n, m;
	vector<vector<int>>w;
	vector<int>lx;
	vector<int>ly;
	vector<bool>visx;
	vector<bool>visy;
	vector<int>link;

	KM(int n, int m){
		this -> n = n;
		this -> m = m;
		w.resize(n+2);
		lx.resize(n+2);
		ly.resize(m+2);
		visx.resize(n+2);
		visy.resize(m+2);
		link.resize(m+2);
		for(int i = 1; i <= n; i++)w[i].resize(m+2, 0), lx[i] = -INF, visx[i] = 0;
		for(int i = 1; i <= m; i++)ly[i] = 0, visy[i] = 0, link[i] = 0;
	}

	bool dfs(int x){
		visx[x] = 1;
		for(int i = 1; i <= m; i++){
			if(!visy[i] && lx[x] + ly[i] == w[x][i]){
				visy[i] = 1;
				if(!link[i] || dfs(link[i])){
					link[i] = x;
					return 1;
				}
			}
		}
		return 0;
	}

	bool km(){
		for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)lx[i] = max(lx[i], w[i][j]);
		for(int i = 1; i <= n; i++){
			while(1){
				for(int i = 1; i <= n; i++)visx[i] = 0;
				for(int i = 1; i <= m; i++)visy[i] = 0;
				if(dfs(i))break;
				int d = INF;
				for(int j = 1; j <= n; j++){
					if(visx[j]){
						for(int k = 1; k <= m; k++){
							if(!visy[k])d = min(d, lx[j] + ly[k] - w[j][k]);
						}
					}
				}
				if(d == INF)return 0;
				for(int j = 1; j <= n; j++)if(visx[j])lx[j] -= d;
				for(int j = 1; j <= m; j++)if(visy[j])ly[j] += d;
			}
		}
		return 1;
	}
};

char c;
array<int, 2> p[105], h[105];
int cntp, cnth;

void solve(){
	int n, m;
	while(cin >> n >> m){
		if(n == 0 && m == 0)return ;
        cntp = cnth = 0;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				cin >> c;
				if(c == 'm'){
					p[++cntp][0] = i;
					p[cntp][1] = j;
				}
				else if(c == 'H'){
					h[++cnth][0] = i;
					h[cnth][1] = j;
				}
			}
		}
		KM km(cntp, cnth);
		for(int i = 1; i <= cntp; i++){
			for(int j = 1; j <= cnth; j++){
				km.w[i][j] = -abs(p[i][0] - h[j][0]) - abs(p[i][1] - h[j][1]);
			}
		}
		int ans = 0;
		for(int i = 1; i <= cnth; i++){
			ans += km.w[km.link[i]][i];
		}
		cout << -ans << '\n';
	}
}

一般图最大匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
struct Blossom {
    int n;                  // 顶点数量
    int tmp;                 // LCA查找用的标记
    vector<int> match;      // 匹配数组：match[u]表示u匹配的顶点（0表示未匹配）
    vector<int> f;          // 并查集父节点，用于缩环（花）
    vector<int> pre;        // 增广路前驱：pre[v]表示v在增广路中的前一个顶点
    vector<int> vis;        // 颜色标记：0-未染色，1-黑色，2-白色
    vector<int> id;         // LCA查找用的临时标记
    queue<int> q;           // BFS队列
    vector<vector<int>> e;  // 邻接表：用vector<vector<int>>存储边
    // 构造函数：初始化顶点数为n
    Blossom(int n) {
        this->n = n;
        match.assign(n + 1, 0);
        f.resize(n + 1);
        pre.resize(n + 1);
        vis.resize(n + 1);
        id.resize(n + 1);
        e.resize(n + 1);  // 初始化邻接表，顶点编号从1开始
    }

    // 并查集查找（路径压缩）
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }

    // 寻找x和y在花中的最近公共祖先（LCA）
    int lca(int x, int y) {
        tmp++;  // 每次LCA用新标记，避免冲突
        while (true) {
            if (x) {  // x为有效顶点
                x = find(x);
                if (id[x] == tmp) return x;  // 找到LCA
                id[x] = tmp;
                x = pre[match[x]];  // 沿匹配边向上找
            }
            swap(x, y);  // 交替查找x和y
        }
    }

    // 缩环操作：将环压缩为花（以l为根）
    void blossom(int x, int y, int l) {
        while (find(x) != l) {
            pre[x] = y;
            y = match[x];
            // 若y是白色节点，将其染为黑色并加入队列
            if (vis[y] == 2) {
                vis[y] = 1;
                q.push(y);
            }
            // 合并到同一集合
            if (find(x) == x) f[x] = l;
            if (find(y) == y) f[y] = l;
            x = pre[y];  // 继续处理环上其他节点
        }
    }

    // 从s出发寻找增广路，返回是否找到
    bool augment(int s) {
        // 初始化
        for (int i = 1; i <= n; ++i) {
            vis[i] = 0;
            pre[i] = 0;
            f[i] = i;
        }
        while (!q.empty()) q.pop();

        q.push(s);
        vis[s] = 1;  // 标记为黑色

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            // 遍历所有邻接顶点（改为vector<vector<int>>的遍历方式）
            for (int v : e[u]) {
                // 同一花中或v是白色节点，跳过
                if (find(u) == find(v) || vis[v] == 2) continue;

                if (!vis[v]) {  // 未染色节点
                    vis[v] = 2;  // 标记为白色
                    pre[v] = u;

                    if (!match[v]) {  // 找到增广路终点
                        // 沿增广路更新匹配
                        for (int x = v, last; x; x = last) {
                            last = match[pre[x]];
                            match[x] = pre[x];
                            match[pre[x]] = x;
                        }
                        return true;  // 增广成功
                    } else {  // 继续扩展匹配顶点
                        vis[match[v]] = 1;  // 标记为黑色
                        q.push(match[v]);
                    }
                } else {  // 找到奇环，进行缩环操作
                    int l = lca(u, v);
                    blossom(u, v, l);
                    blossom(v, u, l);
                }
            }
        }
        return false;  // 未找到增广路
    }
};

void solve(){
	int n, m;
    cin >> n >> m;
    Blossom b(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // 添加边
        b.e[u].push_back(v);  // 无向图，双向添加
        b.e[v].push_back(u);

    }
    // 计算最大匹配
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (!b.match[i] && b.augment(i)) {
            ans++;
        }
    }

    // 输出结果
    cout << ans << "\n";
    for (int i = 1; i <= n; ++i) {
        cout << b.match[i] << " \n"[i == n];
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _ = 1;
    //cin >> _;
    while(_--)solve();

    return 0;
}

struct Blossom {
    int n;
    int tmp;
    vector<int> match;
    vector<int> f;
    vector<int> pre;
    vector<int> vis;
    vector<int> id;
    queue<int> q;
    vector<vector<int>> e;
    Blossom(int n) {
        this->n = n;
        match.assign(n + 1, 0);
        f.resize(n + 1);
        pre.resize(n + 1);
        vis.resize(n + 1);
        id.resize(n + 1);
        e.resize(n + 1);
    }

    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }

    int lca(int x, int y) {
        tmp++;
        while (true) {
            if (x) {
                x = find(x);
                if (id[x] == tmp) return x;
                id[x] = tmp;
                x = pre[match[x]];
            }
            swap(x, y);
        }
    }
    void blossom(int x, int y, int l) {
        while (find(x) != l) {
            pre[x] = y;
            y = match[x];
            if (vis[y] == 2) {
                vis[y] = 1;
                q.push(y);
            }
            if (find(x) == x) f[x] = l;
            if (find(y) == y) f[y] = l;
            x = pre[y];
        }
    }
    bool augment(int s) {
        for (int i = 1; i <= n; ++i) {
            vis[i] = 0;
            pre[i] = 0;
            f[i] = i;
        }
        while (!q.empty()) q.pop();

        q.push(s);
        vis[s] = 1;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
			for (int v : e[u]) {
                if (find(u) == find(v) || vis[v] == 2) continue;
                if (!vis[v]) {
                    vis[v] = 2;
                    pre[v] = u;

                    if (!match[v]) {
                        for (int x = v, last; x; x = last) {
                            last = match[pre[x]];
                            match[x] = pre[x];
                            match[pre[x]] = x;
                        }
                        return true;
                    } else {
                        vis[match[v]] = 1;
                        q.push(match[v]);
                    }
                } else {
                    int l = lca(u, v);
                    blossom(u, v, l);
                    blossom(v, u, l);
                }
            }
        }
        return false;
    }
};


一般图最大权匹配

1
2


连通性

点双连通分量 O(n + m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
struct Tarjan{
	int n, dfn, cnt, top;
	vector<vector<int>>e, d;
	//vector<pii>brig;
	vector<int>num, low, s;
	vector<bool>isc;

	Tarjan(int n){
		this -> n = n;
		this -> dfn = 0;
		this -> cnt = 0;
		this -> top = 0;
		e.resize(n+2);
		d.resize(n+2);
		s.assign(n+2, 0);
		isc.assign(n+2, 0);
		low.assign(n+2, 0);
		num.assign(n+2, 0);
		//brig.resize(n+2);
		for(int i = 1; i <= n; i++)e[i].clear(), d[i].clear();
	}

	void dfs(int u, int fa){
		num[u] = low[u] = ++dfn;
		int child = 0;
		s[++top] = u;
		for(auto v : e[u]){
			if(!num[v]){
				child++;
				dfs(v, u);
				low[u] = min(low[u], low[v]);
				if(low[v] >= num[u]){
					isc[u] = 1;
					cnt++;
					while(s[top + 1] != v)d[cnt].push_back(s[top--]);
					d[cnt].push_back(u);
				}

				//if(low[v] > num[u])brig.push_back(pii{u, v});

			}
			else if(v != fa){
				low[u] = min(num[v], low[u]);
			}
		}
		if(fa == 0 && child == 0)d[++cnt].push_back(u);
	}

	void Ta(){
		for(int i = 1; i <= n; i++)if(!num[i]){
			top = 0;
			dfs(i, 0);
		}
	}

};

ll n, m;

void solve(){
	cin >> n >> m;
	Tarjan ta(n);
	for(int i = 1; i <= m; i++){
		int u, v; cin >> u >> v;
		ta.e[u].push_back(v);
		ta.e[v].push_back(u);
	}
	ta.Ta();
	cout << ta.cnt << '\n';
	for(int i = 1; i <= ta.cnt; i++){
		cout << ta.d[i].size() << ' ';
		for(auto x : ta.d[i])cout << x << ' ';
		cout << '\n';
	}
	return ;

}

边双连通分量 O(n + m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
struct Tarjan{
	int n, cnt, dfn;
	stack<int>s;
	vector<vector<int>>ans;
	vector<int>low, num, color;
	vector<vector<pii>>e;

	Tarjan(int n){
		this -> n = n;
		this -> cnt = 0;
		this -> dfn = 0;
		e.resize(n+2);
		ans.resize(n+2);
		low.assign(n+2, 0);
		num.assign(n+2, 0);
		color.assign(n+2, 0);
		for(int i = 1; i <= n; i++)e[i].clear(), ans.clear();
	}

	void dfs(int u, int last){
		low[u] = num[u] = ++dfn;
		s.push(u);
		for(auto [v, com] : e[u]){
			if(com == (last ^ 1))continue;
			if(!num[v]){
				dfs(v, com);
				low[u] = min(low[u], low[v]);
			}
			else low[u] = min(low[u], num[v]);
		}
		if(num[u] == low[u]){
			vector<int>vec;
			vec.push_back(u);
			color[u] = ++cnt;
			while(s.top() != u){
				color[s.top()] = cnt;
				vec.push_back(s.top()); s.pop();
			}
			s.pop();
			ans[cnt] = vec;
		}
	}

	void Ta(){
		for(int i = 1; i <= n; i++)if(!num[i])dfs(i, 0);
	}
};

ll n, m;

void solve(){
	cin >> n >> m;
	Tarjan ta(n);
	for(int i = 1; i <= m; i++){
		int u, v; cin >> u >> v;
		ta.e[u].push_back(pii{v, i << 1});
		ta.e[v].push_back(pii{u, i << 1 | 1});
	}
	ta.Ta();
	vector<int>du(n+2, 0);
	for(int u = 1; u <= n; u++){
		for(auto [v, com] : ta.e[u]){
			if(ta.color[u] != ta.color[v] && (com % 2 == 0)){
				du[ta.color[u]]++;
				du[ta.color[v]]++;
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= ta.cnt; i++){
		if(du[i] == 1)ans++;
	}
	cout << (ans + 1) / 2 << '\n';
	return ;
}

强连通分量 O(n + m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
struct Tarjan{
	int n, cnt, dfn;
	stack<int>s;
	vector<vector<int>>e;
	vector<int>num, low, sccno, sz;

	Tarjan(int n){
		this -> n = n;
		this -> cnt = 0;
		this -> dfn = 0;
		e.resize(n + 3);
		sz.assign(n + 2, 0);
		num.assign(n + 2, 0);
		low.assign(n + 2, 0);
		sccno.assign(n + 2, 0);
		for(int i = 1; i <= n; i++)e[i].clear();
	}

	void dfs(int u){
		s.push(u);
		num[u] = low[u] = ++dfn;
		for(auto v : e[u]){
			if(!num[v]){
				dfs(v);
				low[u] = min(low[v], low[u]);
			}
			else if(!sccno[v]){
				low[u] = min(low[u], num[v]);
			}
		}
		if(low[u] == num[u]){
			cnt++;
			while(1){
				int v = s.top(); s.pop();
				sccno[v] = cnt;
				sz[cnt]++;
				if(u == v)break;
			}
		}

	}

	void Ta(){
		for(int i = 1; i <= n; i++){
			if(!num[i])dfs(i);
		}
	}

};

ll n, m;

void solve(){
	cin >> n >> m;
	Tarjan ta(n);
	ll ans = 0, cnt = 0;
	map<pii, bool>mp;
	for(int i = 1; i <= m; i++){
		int u, v; cin >> u >> v;
		if(!mp[{u, v}]){
			ta.e[u].push_back(v);
			mp[{u, v}] = 1;
		}
	}
	ta.Ta();
	vector<int>cu(n+2, 0);

	for(int u = 1; u <= n; u++){
		for(auto v : ta.e[u]){
			if(ta.sccno[u] != ta.sccno[v]){
				cu[ta.sccno[u]]++;
			}
		}
	}
	for(int i = 1; i <= ta.cnt; i++){
		if(cu[i] == 0){
			cnt++; ans += ta.sz[i];
		}
	}
	if(cnt == 1)cout << ans << '\n';
	else cout << 0 << '\n';
	return ;
}

树

树的重心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int n, m;
int d[N];
int ans = INF;
vector<int>e[N];

void dfs(int u, int fa){
	d[u] = 1;
	int res = 0;
	for(auto v : e[u]){
		if(v == fa)continue;
		dfs(v, u);
		d[u] += d[v];
		res = max(res, d[v]);
	}
	res = max(res, n - d[u]);
	ans = min(ans, res);
}

void solve(){
	cin >> n;
	ans = INF;
	for(int i = 1; i <= n; i++){
		e[i].clear(); d[i] = 0;
	}
	dfs(1, -1);
	cout << ans << '\n';
	return ;
}

树的直径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
//dp
int n, maxlen;
vector<int>dp(N, 0);
vector<bool>vis(N, 0);
vector<pii>e[N];

void dfs(int u){
	vis[u] = 1;
	for(auto [v, w] : e[u]){
		if(vis[v])continue;
		dfs(v);
		maxlen = max(maxlen, dp[u] + dp[v] + w);
		dp[u] = max(dp[u], dp[v] + w);
	}
}

void solve(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		e[i].clear();
		dp[i] = 0;
	}
	maxlen = 0;
	int u, v;
	for(int i = 1; i <= n - 1; i++){
		cin >> u >> v;
		e[u].push_back(pii{v, 1});
		e[v].push_back(pii{u, 1});
	}
	dfs(1);
	cout << maxlen;

}


//两遍dfs
ll n;
vector<int>dis(N, 0);
vector<pii>e[N];

void dfs(int u, int fa, int d){
	dis[u] = d;
	for(auto [v, w] : e[u]){
		if(v != fa)dfs(v, u, d + w);
	}
}

void solve(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		e[i].clear();
		dis[i] = 0;
	}
	int u, v, w;
	for(int i = 1; i <= n - 1; i++){
		cin >> u >> v;
		e[u].push_back(pii{v, 1});
		e[v].push_back(pii{u, 1});

	}

	int pos = 0;
	dfs(1, -1, 0);
	int sum = 0;
	for(int i = 1; i <= n; i++){
		if(dis[i] > sum){
			sum = dis[i];
			pos = i;
		}
	}
	dfs(pos, -1, 0);
	sum = 0;
	for(int i = 1; i <= n; i++){
		if(dis[i] > sum)sum = dis[i];
	}
	cout << sum << '\n';
	return ;

}


https://www.luogu.com.cn/problem/P3629

ll n, k, leaf, dis[N], dp[N], fa[N], maxlen;
vector<pii>e[N];
vector<bool>vis(N, 0);

void dfs(int u, int from, int d, int t){
	dis[u] = d;
	if(t == 2)fa[u] = from;
	for(auto [v, w] : e[u]){
		if(v == from)continue;
		dfs(v, u, d + w, t);
	}
	if(dis[u] > dis[leaf])leaf = u;
}

void dp_tree(int u, int fa){
	for(auto [v, w] : e[u]){
		if(v == fa)continue;
		if(vis[u] && vis[v])w = -1;
		dp_tree(v, u);
		maxlen = max(maxlen, dp[u] + dp[v] + w);
		dp[u] = max(dp[u], dp[v] + w);

	}
}

void solve(){
	cin >> n >> k;
	maxlen = leaf = 0;
	for(int i = 1; i <= n; i++){
		e[i].clear();
		dis[i] = dp[i] = 0;
		fa[i] = 0;
		vis[i] = 0;
	}
	int u, v, w;
	for(int i = 1; i <= n - 1; i++){
		cin >> u >> v;
		e[u].push_back(pii{v, 1});
		e[v].push_back(pii{u, 1});
	}
	dfs(1, 0, 0, 1);
	//cout << leaf << '\n';
	dfs(leaf, 0, 0, 2);
	if(k == 1){
		cout << 2 * (n - 1) - (dis[leaf] - 1) << '\n';
		return ;
	}
	//cout << leaf << '\n';
	//cout << fa[leaf] << '\n';
	for(int i = leaf; i ; i = fa[i]){
		vis[i] = 1;
	}
	dp_tree(1, 0);
	cout << 2 * (n - 1) - (dis[leaf] - 1) - (maxlen - 1) << '\n';
	return ;
}

LCA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
//常数大的倍增
ll n, m, root;
ll deep[N], fa[N][32];
vector<int>e[N];

void dfs(int u, int from){
	deep[u] = deep[from] + 1;
	fa[u][0] = from;
    //从1开始
	for(int i = 1; (1ll << i) <= deep[u]; i++){
		fa[u][i] = fa[fa[u][i-1]][i-1];
	}
	for(int v : e[u]){
		if(v!=from)dfs(v, u);
	}
}

int LCA(int x, int y){
	if(deep[x] < deep[y])swap(x, y);
	for(int i = 20; i >= 0; i--){
		if(deep[x] - (1ll << i) >= deep[y])x = fa[x][i];
	}
	if(x==y)return x;
	for(int i = 20; i >= 0; i--){
		if(fa[x][i] != fa[y][i]){
			x = fa[x][i]; y = fa[y][i];
		}
	}
	return fa[x][0];
}

void solve(){
	cin >> n >> m >> root;
	int u, v;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(root, -1);
	while(m--){
		cin >> u >> v;
		cout << LCA(u, v) << '\n';
	}

}



//常数小 dfs序
ll n, m, R;
vector<int>e[N];
ll dfn[N], dn, mi[20][N];

int get(int u, int v){
	return dfn[u] < dfn[v] ? u : v;
}

void dfs(int u, int from){
	mi[0][dfn[u] = ++dn] = from;
	for(int v : e[u])if(v!=from)dfs(v, u);
}

int LCA(int u, int v){
	if(u == v)return u;
	if((u = dfn[u]) > (v = dfn[v]))swap(u, v);
	int d = __lg(v - u++);
	return get(mi[d][u], mi[d][v - (1 << d) + 1]);
}

void solve(){
	cin >> n >> m >> R;
	int u, v;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(R, 0);
	for(int i = 1; i <= __lg(n); i++){
		for(int j = 1; j + (1 << i) - 1 <= n; j++){
			mi[i][j] = get(mi[i-1][j], mi[i-1][j + (1 << i - 1)]);
		}
	}
	while(m--){
		cin >> u >> v;
		cout << LCA(u, v) << '\n';
	}
	return ;
}



//树上差分
ll n, m, root;
ll deep[N], fa[N][32], D[N], ans;
vector<int>e[N];

void dfs(int u, int from){
	deep[u] = deep[from] + 1;
	fa[u][0] = from;
	for(int i = 1; (1ll << i) <= deep[u]; i++){
		fa[u][i] = fa[fa[u][i-1]][i-1];
	}
	for(int v : e[u]){
		if(v!=from)dfs(v, u);
	}
}

int LCA(int x, int y){
	if(deep[x] < deep[y])swap(x, y);
	for(int i = 20; i >= 0; i--){
		if(deep[x] - (1ll << i) >= deep[y])x = fa[x][i];
	}
	if(x==y)return x;
	for(int i = 20; i >= 0; i--){
		if(fa[x][i] != fa[y][i]){
			x = fa[x][i]; y = fa[y][i];
		}
	}
	return fa[x][0];
}

void dfss(int u, int from){
	for(int v : e[u]){
		if(v==from)continue;
		dfss(v, u);
		D[u] += D[v];
	}
	ans = max(ans, D[u]);
}

void solve(){
	cin >> n >> m;
	int u, v;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 0);
	while(m--){
		cin >> u >> v;
		int r = LCA(u, v);
		int f = fa[r][0];
		D[u]++; D[v]++; D[r]--; D[f]--;
	}
	dfss(1, 0);
	cout << ans << '\n';
	return ;
}


//kru + LCA
ll n, m, q;
bool vis[N];
int fa[N], ss[N];
struct node{
	int u, v, w;
}ee[N];
vector<pii>e[N];
int deep[N], f[N][22], w[N][22];

int find(int k){
	return k==fa[k]?k:fa[k]=find(fa[k]);
}

void un(int u, int v){
	u = find(u); v = find(v);
	if(ss[u] < ss[v])swap(u, v);
	fa[v] = u;
	ss[u] += ss[v];
	return ;
}
void kr(){
	for(int i = 1; i <= n; i++)ss[i] = 1, fa[i] = i;
	sort(ee + 1, ee + 1 + m, [](node a, node b){return a.w > b.w;});
	for(int i = 1; i <= m; i++){
		if(find(ee[i].u) == find(ee[i].v))continue;
		un(ee[i].u, ee[i].v);
		e[ee[i].u].push_back(pii{ee[i].v, ee[i].w});
		e[ee[i].v].push_back(pii{ee[i].u, ee[i].w});
	}
}

void dfs(int u){
	vis[u] = 1;
	for(auto [v, val] : e[u]){
		if(vis[v])continue;
		w[v][0] = val;
		f[v][0] = u;
		deep[v] = deep[u] + 1;
		dfs(v);
	}
}

int LCA(int u, int v){
	if(find(u) != find(v)) return -1;
	if(deep[u] < deep[v])swap(u, v);
	int ans = INF;
	for(int i = 20; i >= 0; i--){
		if(deep[u] - (1ll << i) >= deep[v]){
			ans = min(ans, w[u][i]);
			u = f[u][i];
		}
	}
	if(u==v)return ans;
	for(int i = 20; i >= 0; i--){
		if(f[u][i] != f[v][i]){
			ans = min(ans, min(w[u][i], w[v][i]));
			u = f[u][i];
			v = f[v][i];
		}
	}
	ans = min(ans, min(w[u][0], w[v][0]));
	return ans;
}

void solve(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> ee[i].u >> ee[i].v >> ee[i].w;
	}
	kr();
	for(int i = 1; i <= n; i++){
		if(!vis[i]){
			deep[i] = 1;
			dfs(i);
			w[i][0] = INF;
			f[i][0] = i;

		}
	}
	for(int i = 1; i <= 20; i++){
		for(int j = 1; j <= n; j++){
			f[j][i] = f[f[j][i-1]][i-1];
			w[j][i] = min(w[j][i-1], w[f[j][i-1]][i-1]);
		}
	}
	cin >> q;
	while(q--){
		int u, v; cin >> u >> v;
		cout << LCA(u, v) << '\n';
	}
}

评论区仅供交流，有问题请提 issue 反馈。