关于Tarjan的疑问
查看原帖
关于Tarjan的疑问
220824
yyz1005楼主2022/5/21 12:26

RT,之前一直都是 RE

原代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
const int M = 1000010;
int n,m,s;
struct qes{
	int fri,nob;//quest[i]中有 "j,v" 表示第v个问题是求i和j的lca 
};
vector<qes> quest[N];
int fa[N];
bool vis[N];
//链式前向星 
struct Edge{
	int from;
	int to;
	int next;
} edge[N*2];
int head[N],cnt = 0;
void add(int u,int v){
	cnt++;
	edge[cnt].from = u;
	edge[cnt].to = v;
	edge[cnt].next = head[u];
	head[u] = cnt;
}
//初始化 
void init(){
	for(int i = 1; i <= n; i++){
		fa[i] = i;
		vis[i] = false;
	}
}
//主体部分
int findfather(int x){//找父亲
	if(fa[x]!=x){fa[x] = findfather(fa[x]);return fa[x];}//找父亲 
	return x;
}
int answer[M];
void dfs(int id,int fath){
	for(int i = head[id]; i; i = edge[i].next){
		if(edge[i].to==fath) continue;
		dfs(edge[i].to,id);
		fa[edge[i].to] = id;
	}
	for(int i = 0; i <= quest[id].size()-1; i++){
		if(vis[quest[id][i].fri]){
			answer[quest[id][i].nob] = findfather(quest[id][i].fri);
		}
	}
	vis[id] = true;
} 
//主函数 
int main(){
	cin >> n >> m >> s;
	init();
	for(int i = 1; i < n; i++){
		int u,v;
		cin >> u >> v;
		add(u,v);
		add(v,u);
	}
	for(int i = 1; i <= m; i++){
		int u,v;
		cin >> u >> v;
		if(u==v) answer[i] = u;
		else {
			quest[u].push_back((qes){v,i});
			quest[v].push_back((qes){u,i});
		}
	}
	dfs(s,s);
	for(int i = 1; i <= m; i++) cout << answer[i] << endl;
	return 0;
}

但是将 dfs 函数

//之前的
void dfs(int id,int fath){
    for(int i = head[id]; i; i = edge[i].next){
        if(edge[i].to==fath) continue;
        dfs(edge[i].to,id);
        fa[edge[i].to] = id;
    }
    for(int i = 0; i <= quest[id].size()-1; i++){
        if(vis[quest[id][i].fri]){
            answer[quest[id][i].nob] = findfather(quest[id][i].fri);
        }
    }
    vis[id] = true;
} 

改为(改动的行后有 //* 的标记)

//现在的
//vis数组的类型改为 int
void dfs(int id,int fath){
	vis[id] = 1;//*
	for(int i = head[id]; i; i = edge[i].next){
		if(edge[i].to==fath) continue;
		dfs(edge[i].to,id);
		fa[edge[i].to] = id;
	}
	for(int i = 0; i < quest[id].size(); i++){
		if(vis[quest[id][i].fri]==2){//*
			answer[quest[id][i].nob] = findfather(quest[id][i].fri);
		}
	}
	vis[id] = 2;//*
} 

后就AC了,之前是全部RE,为什么会这样?

2022/5/21 12:26
加载中...