割点
对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点（又称割顶）。
如果尝试删除每个点，并且判断这个图的连通性，那么复杂度会特别的高。所以要介绍一个常用的算法：Tarjan。
首先，上一个图：
很容易的看出割点是 2，而且这个图仅有 2 这一个割点。
首先，按照 dfn 序给他打上时间戳（访问的顺序）。
这些信息被保存在一个叫做 dfn 的数组中。
还需要另外一个数组 low ，用它来存储不经过其入边（你有多个那么就看你遍历到了哪个）能到达的最小的时间戳。
例如 \(2\) 的话是 \(1\)，\(5\) 和 \(6\) 是 \(3\)。
然后开始 DFS，判断某个点是否是割点的根据是：对于某个顶点 \(x\) ，如果存在至少一个顶点 \(y\) （ \(x\) 的出边），使得 \(low_v>=dfn_u\) ，即不能回到祖先，那么 \(x\) 点为割点。为什么这句话是对的呢？假设当前节点是在下面，他的入边在中间，如果他不经过他的入边访问不到上面的点，那么这个点一定是割点了。
另外，如果搜到了自己（在环中），如果他有两个及以上的出边，那么他一定是割点了，如果只有一个出边，那么把它删掉，不会有任何的影响。比如下面这个图，此处形成了一个环，从 \(1\) 走：
在访问 \(1\) 的出边时候，假设先 dfn 到了 \(2\)，然后标记用过，然后递归往下，来到了 \(4\)，\(4\) 又来到了 \(3\)，当递归回溯的时候，会发现 3 已经被访问过了，所以 \(1\) 不是割点。
然后访问 \(2\) ，\(2\) 的出边多了一个 \(5\)，加上之前访问的 \(4\) 一共两个。所以 $2 $是割点。
更新 low 的伪代码如下：
如果 v 是 u 的出边 low[u] = min(low[u], low[v]);
否则
low[u] = min(low[u], dfn[v]);/*
洛谷 P3388 【模板】割点（割顶）
*/
#include <bits/stdc++.h>
using namespace std;
int n, m; // n：点数 m：边数
int dfn[100001], low[100001], inde, res;
// dfn：记录每个点的时间戳
// low：能不经过入边到达最小的编号，inde：时间戳，res：答案数量
bool vis[100001], flag[100001]; // flag: 答案 vis：标记是否重复
vector<int> edge[100001]; // 存图用的
void Tarjan(int u, int father) // u 当前点的编号，father 自己爸爸的编号
{
vis[u] = true; // 标记
low[u] = dfn[u] = ++inde; // 打上时间戳,他最小也能到自己
int child = 0; // 每一个点出边数量
for (auto v : edge[u]) // 访问这个点的所有邻居 （C++11）
{
if (!vis[v]) {
child++; // 多了一个出边
Tarjan(v, u); // 继续
low[u] = min(low[u], low[v]); // 更新能到的最小节点编号
if (father != u && low[v] >= dfn[u] &&
!flag
[u]) // 主要代码
// 如果不是自己，且不通过入边返回的最小点符合割点的要求，并且没有被标记过
// 要求即为：删了入边连不上去了，即为最多连到入边
{
flag[u] = true;
res++; // 记录答案
}
} else if (v != father)
low[u] =
min(low[u], dfn[v]); // 如果这个点不是自己，更新能到的最小节点编号
}
if (father == u && child >= 2 &&
!flag[u]) // 主要代码，自己的话需要 2 个出边才可以，如果这个点已经是割点，那么不能重复计算。
{
flag[u] = true;
res++; // 记录答案
}
}
int main() {
cin >> n >> m; // 读入数据
for (int i = 1; i <= m; i++) // 注意点是从 1 开始的
{
int x, y;
cin >> x >> y;
edge[x].push_back(y);
edge[y].push_back(x);
} // 使用 vector 存图
for (int i = 1; i <= n; i++) // 因为 Tarjan 图不一定连通
if (!vis[i]) {
inde = 0; // 时间戳初始为 0
Tarjan(i, i); // 从第 i 个点开始，入边为自己
}
cout << res << endl;
for (int i = 1; i <= n; i++)
if (flag[i]) cout << i << " "; // 输出结果
for (int i = 1; i <= n; i++) cout << low[i] << endl;
return 0;
}割边
和割点差不多，还叫做割桥。对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。如下图，割边有：\(\{1,2\} , \{2,5\}\)。
和割点差不多，只要改一处： \(low_v>dfn_u\) 就可以了，而且不需要考虑根节点的问题。
割边是和是不是根节点没关系的，原来求割点的时候是指点 \(y\) 是不可能不经过父节点 \(x\) 为回到祖先节点（包括父节点），所以顶点 \(x\) 是割点。如果 \(low_v=dfn_u\) 表示还可以回到父节点，如果顶点 \(y\) 不能回到祖先也没有另外一条回到入边的路，那么 \(u-v\) 这条边就是割边。
#include<bits/stdc++.h>
using namespace std;
int n, m;
int dfn[100001], low[100001], index, res, tot;
bool vis[100001], cut[500001];
pair <int, int> edge[500001]; //边对应的两个点
vector <pair<int,int> > G[100001]; // 新增一个元素记录边的编号
void Tarjan(int x, int fa){
vis[x] = true; low[x] = dfn[x] = ++index;
int child = 0;
for (int i = 0; i < G[x].size(); i++){
int y = G[x][i].first, z = G[x][i].second;
if (!vis[y]){
child++; Tarjan(y,x);
low[x] = min(low[x], low[y]);
if (low[y] > dfn[x] && !cut[x]) cut[z] = true, res++;
}else if(y != fa) low[x] = min(low[x], dfn[y]);
}
}
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++){
int x, y; scanf("%d%d", &x, &y);
G[x].push_back(make_pair(y, ++tot)); G[y].push_back(make_pair(x, tot));
edge[tot] = make_pair(x, y);
}
for (int i = 1; i <= n; i++)
if (!vis[i]) index = 0, Tarjan(i, i);
printf("%d\n", res);
for (int i = 1; i <= m; i++)
if (cut[i]) printf("%d %d\n", edge[i].first, edge[i].second);
return 0;
}点双联通分量
点双联通图的定义是：没有割点的无向联通图。如图，该图有 \(3\) 个点联通分量（不知道联通分量出门左转百度）：\(\{1,2\},\{2,5\},\{2,3,4\}\)（不唯一，比如 \(2,5\) 可以换成 \(2,3\)）。
判断一个图是否是点双联通图只要照着定义跑一边割点就可以判断了，但是大多数题目都是让求出点联通分量。
不超过两个点的子图一定点双联通，因为他不会有割点，而三个点的话只要组成一条链，中间那个点就是割点。
如果有超过两个点的图，只要这个图的所有点都包含在一个简单环中，那么他一定是点联通图。
扩展到点联通分量，点联通分量一定要是极大的。如果一个点能回到他的上面即为他的祖宗，那么这就是一个简单环，但是如果还有一个点还能回到前者上面的上面，即为前者祖宗的祖宗，那么选择后者肯定比前者优秀，因为后者包含的范围更大。一句话总结：子孙没有指向这个点的祖先的边，却有指向这个点的边
而且呢，必须只包含在一个环中，不能是多个，如下图，如果令所有的点为点双联通分量，显然他们在两个环中，\(2\) 就是割点。
开一个栈，如果遇到一个点是第一次访问，那么把它压入栈中。如果当前的点与他的祖先组成了割点，那么就把中间过程的所有点弹出来，直到他的祖先被弹出为止。弹出的所有点就是一个点双联通分量。
为什么是这样做是对的？因为割点是在回溯中判断的，越早访问的点，回溯的越晚，图的规模越小。反之同理。
结合下面模拟理解。
访问 \(1\)，访问 \(2\) ，访问 \(5\)，\(5\) 返回 \(2\)，\(2\) 访问 \(3\)，\(3\) 访问 \(4\)，\(4\) 访问 \(2\)，\(2\) 已经访问过了，不继续扩展，于是 \(2\) 先返回到 \(1\)，发现 \(2\) 是割点，加入点双联通分量 \({2,5}\)，然后从 \(2\) 返回到 \(4\)，\(4\) 返回到 \(3\)，返回到 \(2\)，\(2\) 返回到 \(1\)，发现 \(2\) 还是割点，于是加入点双联通分量 \({2,3,4}\)。还有一个点双联通分量 \({1,2}\)，怎么办？额，只从 \(1\) 开始找，从每个点开始进行 Tarjan 就好了。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, dfn, cnt, dfn[N], low[N], cut[N];
vector <int> G[N], ans[N];
stack <int> st;
void Tarjan(int x, int fa) {
dfn[x] = low[x] = ++dfn; st.push(x);
int child = 0 ;
for (int i = 0; i < G[x].size(); i++) {
int y = G[x][i];
if(!dfn[y]) {
child++; Tarjan(y, x); low[x] = min(low[y] , low[x]);
if(low[y] >= dfn[x]) {
cut[x] = 1; ans[++cnt].push_back(x);
while(x!=st.top()) ans[cnt].push_back(st.top()), st.pop(); //统计答案
}
}else if (dfn[x] > dfn[y] && y != fa) low[x] = min(dfn[y], low[x]); //y能走到x（一个环就有可能）
}
if (fa == 0 && child == 1) cut[x] = 0; //2个点，上面会误判 x 为割点。
if (fa == 0 && child == 0) G[++cnt].push_back(x); //一个点
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++){
int x, y; scanf("%d%d", &x, &y);
G[x].push_back(y); G[y].push_back(x);
}
for (int i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i, 0);
printf("%d\n", cnt);
for (int i = 1; i <= cnt; i++)
for (int j = 0; j < ans[i].size(); j++)
printf("%d%c", ans[i][j], (j == ans[i].size() - 1 ? '\n' :' '));
return 0;
}边双联通分量
顾名思义，边双联通分量就是没有割边的无向联通图。如下图，边双联通分量是且仅是整个图。
相比于点双联通分量，边双联通分量就很简单了。
进行一次 Tarjan 求出所有的割边，把这些割边 "删掉"（就是在求联通分量的时候不访问），然后统计所有的联通分量就是边双联通分量了。简单吧？为什么边双联通分量没有点双联通分量那么难呢？因为一条边最多存在于一个子图中，而一个点可以存在于多个子图中。所以可以删割边，不能删割点了。
#include<bits/stdc++.h>
using namespace std;
int n, m;
int dfn[100001], low[100001], index, tot;
bool vis[100001], cut[500001];
pair <int, int> edge[500001]; //边对应的两个点
vector <pair<int,int> > G[100001]; // 新增一个元素记录边的编号
void Tarjan(int x, int fa){
vis[x] = true; low[x] = dfn[x] = ++index;
int child = 0;
for (int i = 0; i < G[x].size(); i++){
int y = G[x][i].first, z = G[x][i].second;
if (!vis[y]){
child++; Tarjan(y,x);
low[x] = min(low[x], low[y]);
if (low[y] > dfn[x] && !cut[x]) cut[z] = true;
}else if(y != fa) low[x] = min(low[x], dfn[y]);
}
}
vector <int> ans;
void dfn(int x){//求图中的联通分量
for (int i = 0; i < G[x].size(); i++){
int y = G[x][i].first, z = G[x][i].second;
if (vis[y] || cut[z]) continue; //不重复不是割点
vis[y] = 1; ans.push_back(y);
dfn(y);
}
}
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++){
int x, y; scanf("%d%d", &x, &y);
G[x].push_back(make_pair(y, ++tot)); G[y].push_back(make_pair(x, tot));
edge[tot] = make_pair(x, y);
}
for (int i = 1; i <= n; i++)
if (!vis[i]) index = 0, Tarjan(i, i);
memset(vis, 0, sizeof(vis)); //节约空间
for (int i = 1; i <= n; i++)
if (!vis[i]){
vis[i] = 1;
ans.clear(); ans.push_back(i);
dfn(i);
for (int i = 0; i < ans.size(); i++) printf("%d%c", ans[i], (i == ans.size() - 1 ? '\n' : ' '));
}
return 0;
}强连通分量
所谓的强连通图，就是一个有向图中，任意两个点互相都能到达，那么强连通分量就是极大的强连通图了。如下图，强联通分量有：\(\{1,2,3\},\{4\},\{5\}\)。
如上面那张图，\(1, 2, 3\) 所有的点都在一个有向的简单环中，\(4\) 和 \(5\) 都是一个孤立的点。那么可以直接大胆下结论：
- 只有一个点的子图一定是强连通的子图
- 一个强连通子图中的所有点，一定在一个简单环内（有向图中的简单环是由回祖路造成的，回祖路是从自己连向自己的祖先的边）。
要求的是强连通分量，按照之前的套路，还是要要满足一个点的联通子图中：子孙没有指向这个点的祖先的边，却有指向这个点的边。
还是需要一个栈，遇到一个点被访问过，那么把它加入栈，如果遇到的这个点已经被访问过，那么它们中间的子图都是强连通的（同一个节点第一次被访问的位置到第二次被访问位置中间所有的点，包括被访问两次的点本身）。但是不确定这个子图是不是极大的，因为并不是和点双联通分量用割点方法判断的，你想想，既然不用割点判断，那么为什么要进行 Tarjan 呢？
不要忘记了的 dfn 和 low 数组，因为之前提到需要满足 子孙没有指向这个点的祖先的边，却有指向这个点的边 所以看看它不经过自己，能不能到自己的祖宗，为什么只判断自己就够了？因为如果下面的点能到这个点的祖宗，那么自己可以走到那个点后再到自己的祖宗嘛（有点绕口令）。所以，只需要判断 dfn[x] == low[x] 就可以知道是不是一个强连通分量了。
相信你会写了
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, num, cnt, dfn[N], low[N], cut[N], res, vis[N];
vector <int> G[N], ans[N];
stack <int> st;
void Tarjan(int x) {
dfn[x] = low[x] = ++num; st.push(x); vis[x] = 1;
int child = 0 ;
for (int i = 0; i < G[x].size(); i++) {
int y = G[x][i];
if(!dfn[y]) {
child++; //child没用 打模板习惯打上去了
Tarjan(y); low[x] = min(low[y] , low[x]);
}else if(vis[y]) low[x] = min(dfn[y], low[x]); //必须要判断它的 vis，因为下面可能会取消vis标记
}
if (dfn[x] == low[x]){
int y = -1; cnt++;
while (x != y){
ans[cnt].push_back(y = st.top()); vis[st.top()] = 0; // 以后可能还要用到这个点的，因为一个点可能在两个强联通分量中。
st.pop();
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++){
int x, y; scanf("%d%d", &x, &y);
G[x].push_back(y);
}
for (int i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i);
printf("%d\n", cnt);
for (int i = 1; i <= cnt; i++)
for (int j = 0; j < ans[i].size(); j++)
printf("%d%c", ans[i][j], (j == ans[i].size() - 1 ? '\n' :' '));
return 0;
}缩点
缩点就是把有向图中每个强连通分量缩成若干个超级点。如下图，可以把这个图缩成三个点：\(A,B,C\)，\(A\) 对应 \(1 \ 2 \ 3\)，\(B\) 对应 \(4\)，\(C\) 对应 \(5\)。缩点后的图具有一个性质：一个有向无环图（DAG），可以在这个图上进行很多操作。所以缩点是 Tarjan 最实用的算法了，一般题目是以某个算法为主（常是 DP），以缩点为辅。所以只学好缩点是做不出题的，还要学一下其他的算法。下面的 2-SAT 就用到了缩点。
上面的代码，已经求出了所有的强连通分量和它们包括的点，所以直接将每个强连通分量转成点就可以了。如果两个点之间右边，那么它们所在的强连通分量，也就是的超级点也会有边，这样的话可能有重边，但是边权不一定相同，边权视情况而定。具体实现见代码。
如果你学会了强连通分量，相信这对你很简单。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, num, cnt, dfn[N], low[N], cut[N], res, vis[N], tot, color[N];
vector <int> G[N], ans[N], G2[N];
stack <int> st;
void Tarjan(int x) {
dfn[x] = low[x] = ++num; st.push(x); vis[x] = 1;
int child = 0 ;
for (int i = 0; i < G[x].size(); i++) {
int y = G[x][i];
if(!dfn[y]) {
child++; //child没用 打模板习惯打上去了
Tarjan(y); low[x] = min(low[y] , low[x]);
}else if(vis[y]) low[x] = min(dfn[y], low[x]); //必须要判断它的 vis，因为下面可能会取消vis标记
}
if (dfn[x] == low[x]){
int y; cnt++;
do{
ans[cnt].push_back(y = st.top()); vis[y] = 0; color[y] = cnt;
// 以后可能还要用到这个点的，因为一个点可能在两个强联通分量中。
st.pop();
}while (x != y);
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++){
int x, y; scanf("%d%d", &x, &y);
G[x].push_back(y);
}
for (int i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i);
for (int i = 1; i <= n; i++) {//这里不是 O(n^2) 而是 O(2 * n) 的
for (int j = 0; j < G[i].size(); j++){
if(color[i] != color[G[i][j]]) //不能自己连自己
G2[color[i]].push_back(color[G[i][j]]); //DAG
}
}
for (int i = 1; i <= cnt; i++){
printf("%d:", i);
for (int j = 0; j < G2[i].size(); j++)
printf(" %d", G2[i][j]);
puts("");
}
return 0;
}为了感受一下缩点的强大，一起来做一道入门题（不会 DAG 上 DP 者左转百度）：
给定一个 \(n\) 个点 \(m\) 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
这道题不是什么最大生成树，因为它可以重复经过一个点。这可怎么办呢？下面展示一下缩点题目的思考过程：
- 这道题图论（最大生成树) 好像不可做。
- 有向图，可以缩点？
- 缩点后能用什么算法？
- 想了一段时间：哦，好像在 DAG 上 DP 就行了。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 4, M = 1e5 + 5;
int n, m, tot, cnt;
int w[N], dfn[N], low[N], vis[N], color[N], in[N], dp[N], sum[N];
stack <int> st;
vector <int> G[N], G2[N];
queue <int> q;
void Tarjan(int x){
st.push(x); vis[x] = 1;
dfn[x] = low[x] = ++tot;
for (int i = 0; i < G[x].size(); i++){
int y = G[x][i];
if (!dfn[y]){
Tarjan(y); low[x] = min(low[y], low[x]);
} else if (vis[y]) low[x] = min(dfn[y], low[x]);
}
if (dfn[x] == low[x]){
int y; cnt++;
do{
y = st.top(); st.pop(); //dp[y] = w[y];
vis[y] = 0; color[y] = cnt;
}while(x != y);
}
}
void solve(){
for (int i = 1; i <= cnt; i++)
if(!in[i]) q.push(i), dp[i] = sum[i];
while (!q.empty()){
int x = q.front(); q.pop();
for (int i = 0; i < G2[x].size(); i++){
int y = G2[x][i];
dp[y] = max(dp[y], dp[x] + sum[y]);
if (!--in[y]) q.push(y);
}
}
printf("%d\n", *max_element(dp + 1, dp + cnt + 1));
}
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
for (int i = 1; i <= m; i++){
int x, y; scanf("%d%d", &x, &y);
G[x].push_back(y);
}
for (int i = 1; i <= n; i++) if (!dfn[i]) Tarjan(i);
for (int i = 1; i <= n; i++) sum[color[i]] += w[i];
for (int x = 1; x <= n; x++)
for (int i = 0; i < G[x].size(); i++){
int y = G[x][i];
if (color[x] != color[y]) {
G2[color[x]].push_back(color[y]);
in[color[y]]++;
}
}
solve();
return 0;
}2-SAT
一天，小 Y 去给他的 GF 买饭，他一共有 \(n\) 个 GF（假设有 \(3\) 个），每个 GF 有 \(2\) 个要求，满足其中一个即可：
GF 1 的要求：
- 不要肉
- 要菜
GF 2 的要求：
- 要肉
- 要菜
GF 3 的要求：
- 不要肉
- 不要菜
小 Y 想得到 GF 的欢心，但是他的 GF 的问题实在是太刁钻了，所以小 Y 希望满足每一个女朋其中一个的条件。显然，这个问题有两个个答案：要菜，不要肉和不要肉，要菜。
发现，每个 GF 的条件只有 2 个，实际上，条件 $ \ge 3$ 的时候已经被证明了是 NP 问题，只能暴力求解（我可不证明啊）。但是，对于条件只有 \(2\) 个 的可以用 Tarjan 求解。注意： 条件 $ \ge 3$ 是指的每个 GF 的条件$ \ge 3$，而不是条件的总数。条件的总数可能有多个。
不妨设 要肉为 \(a\)，不要肉为 \(-a\)，要菜为 \(b\)，不要菜为 \(-b\)。那么对于每一个 GF，如果他一个条件不满足，那么另一个条件就必须满足。例如 GF 1，如果只满足她的一个条件，那么可以满足：\(-a\) 和 \(b\) 或 \(a\) 和 \(-b\)。
发现，对于每个 GF，将她的一个条件取反，与另一个条件连一条有向边（ \(-a\) 的编号 实际上是 \(a + 3\) 即为 \(a + n\)），会形成一个有 \(2 \times 3\)（\(2 \times n\)）个节点的图，如下图：
可以发现，无解当且仅当 \(a\) 与 \(-a\) 或 \(b\) 与 \(-b\) 在一个强连通分量中，反之有解。
然后，将图缩点，如下图。仔细观察这个图，发现构成的是一张拓扑图。这张拓扑图中，如果 \(x\) 可以到达 \(y\)，那么选择则 \(x\) 的话，\(y\) 也必须选择（仔细想一想）。那么，你可以利用强连通分量的时间戳来得到反向的拓扑序。
但是，对于一组条件，可能会有多组解同时成立。要怎样判断给每个变量赋的值是否恰好构成一组解呢？发现，可以用超级点的编号来得到反向的拓扑序。那么结论就是：对于有 \(a\) 与 \(-a\) 的强连通分量中，选择拓扑序较大的点。
#include <bits/stdc++.h>
using namespace std;
const int N = (1e6 + 10) * 2;
int low[N], dfn[N], color[N];
bool vis[N];
stack<int>st;
int n, m, tot, cnt;
vector <int> G[N];
void Tarjan(int x)
{
low[x] = dfn[x] = ++tot;
st.push(x); vis[x] = 1;
for (int i = 0; i < G[x].size(); i++){
int y = G[x][i];
if (!dfn[y]){
Tarjan(y);
low[x] = min(low[y], low[x]);
}else if(vis[y]) low[x] = min(low[y], low[x]);
}
if (low[x] == dfn[x]){
int y; cnt++;
do{
y = st.top(); st.pop();
vis[y] = 0; color[y] = cnt;
}while(x!=y);
}
}
bool check()
{
for (int i = 1; i <= 2 * n; i++) if (!dfn[i]) Tarjan(i); //Tarjan找强连通分量
for (int i = 1; i <= n; i++) if(color[i] == color[i + n]) return 0; //a和-a在同一个强连通分量，无解。
return 1;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++){ //用a表示条件a，a+n表示条件-a。
int a, b, x, y; scanf("%d%d%d%d", &a, &x, &b, &y);
G[a + (x ^ 1) * n].push_back(b + y * n); //连边(-a，b)
G[b + (y ^ 1) * n].push_back(a + x * n); //连边(-b，a)
}
if(check())
{
puts("POSSIBLE");
for (int i = 1; i <= n; i++) printf("%d ", color[i] > color[i + n]);
}else puts("IMPOSSIBLE");
return 0;
}LCA
Tarjan 求 LCA 是所有求 LCA 的方法中最快的，是离线算法。而且预处理和查询的常数都是最小的，复杂度是常数较大的 \(O(n + m + q)\)（要先存输入，并且用到了并查集）。对于数据范围大，查询又多的题目有奇效。下面直接讲算法：
每进入一个节点 \(x\) 的 Tarjan，就把当前的树看作以 \(x\) 为根节点的子树，再搜索其他的节点。每搜索完一个点后，如果该点和另一个已搜索完点 \(y\) 为需要查询 LCA 的一对点，则这两点的 LCA 为 \(y\) 的现在的祖先。
- 建图，用两个
vector来保存这颗树，与所有的查询（查询 \(x\) 与 \(y\)，那么给 \(x\) 和 \(y\) 连一条双向边，用数组存浪费空间会 MLE）。 - 从根节点开始 Tarjan。
- 在递归函数中，先将自己的入边设置为自己（把当前的树看作以自己为根的子树，令当前点为 \(x\)），然后找与他相邻的点，如果没有被访问，那么就对这个点 Tarjsan，结束后把这个点的子树与 \(x\) 这个点合并，使用并查集。
- 每搜索完一个点后，判断它能不能与一个点构成的点对是查询的 LCA，用
vector\(O(1)\) 判断。如果是的话算出答案保存在答案数组中。 - 在 Tarjan结束后输出答案。
细心的小朋友可以发现，"如果是的话算出答案保存在答案数组中" 这句话中的 算出答案的方法我还没介绍呢。没关系，用并查集找爹就可以了。还有一个问题是：输出要按照输入的顺序，可以在 vector 加上一个关键字。。
#include <bits/stdc++.h>
using namespace std;
const int N = 500000 + 5;
int n, q, s, vis[N], ans[N];
int f[N];
vector <int> G[N];
vector <pair<int, int> > ask[N];
int find(int k){
if(f[k] == k) return f[k];
return f[k] = find(f[k]);
}
void merge(int a,int b){
int A = find(a), B = find(b);
if(A != B) f[B] = A;
}
void Tarjan(int x){
f[x] = x; vis[x] = 1;
for (int i = 0; i < G[x].size(); i++){
int y = G[x][i];
if (!vis[y]){
Tarjan(y); merge(x, y);
}
}
for (int i = 0; i < ask[x].size(); i++){
int y = ask[x][i].first, z = ask[x][i].second;
if(vis[y]) ans[z] = find(y);
}
}
int main(){
scanf("%d%d%d", &n, &q, &s);
for (int i = 1; i < n; i++){
int x, y; scanf("%d%d", &x, &y);
G[x].push_back(y); G[y].push_back(x);
}
for (int i = 1; i <= q; i++){
int x, y; scanf("%d%d", &x, &y);
ask[x].push_back(make_pair(y, i)); ask[y].push_back(make_pair(x, i));
}
Tarjan(s);
for (int i = 1; i <= q; i++)
printf("%d\n", ans[i]);
return 0;
}撒花！