气抖冷,蒟蒻找了好久错误都没过
查看原帖
气抖冷,蒟蒻找了好久错误都没过
246800
wocaicai楼主2020/6/5 19:05

rt 找了好久错误都看不出来 , 一直50分 , 后面改的连变量都感觉和第一篇题解都差不多了啊。。。 求大佬帮助qwq

#include<bits/stdc++.h>
using namespace std ;
#define maxn 700010 
//#define int long long
#define kkk signed main
int read(){
	int ans = 0 , f = 1 ; char ch = getchar() ;
	while ( ch < '0' || ch > '9') {	 if( ch == '-' )  f = -1 ; ch = getchar() ; }
	while ( ch >= '0' && ch <= '9' ) ans =  ( ans << 3 ) +  ( ans << 1 ) + ch - '0' , ch = getchar() ;
	return ans * f ;
}
int dfn[maxn] , low[maxn] , calc ;
int w[maxn] , dep[maxn] , son[maxn] , siz[maxn] , top[maxn] , fa[maxn]; 
int n , m , q , tot ; 
//int head[maxn] , to[maxn] , nxt[maxn] ; 
int st[maxn] , tp ;  
struct Graph{
	int head[maxn << 1] , to[maxn << 1] , nxt[maxn << 1],  cnt = 0 ;
	void addedge(int u , int v){
		to[++cnt] = v ;
		nxt[cnt] = head[u] ; 
		head[u] = cnt;  
		to[++cnt] = u ; 
		nxt[cnt] = head[v] ; 
		head[v] = cnt ; 
	}
} G , T ;
void tarjan(int u ){
	dfn[u] = low[u] = ++calc ; st[++tp] = u ;
	for(int i = G.head[u] ; i ; i = G.nxt[i]){
		int v = G.to[i] ; 
		if(!dfn[v]){
			tarjan(v) ; 
			low[u] = min(low[u] , low[v]) ; 
			if(low[v] >= dfn[u]){
				T.addedge(++tot , u) ; 
				printf("tot : %lld u : %lld \n" , tot , u)  ; 
				int x = 0 ; 
				do{
					 x = st[tp--] ; T.addedge(tot , x) ;  //
				}while(x!=v);
			} 
		}
		else low[u] = min(low[u] , dfn[v]) ; 
	}
}
void dfs1(int u , int dp){
//	printf("u : %lld dp : %lld\n" , u , dp) ; 
	siz[u] = 1 , dep[u] = dp ; 
	int maxson = 0 ;// printf("T : %lld \n" , T.head[u]) ; 
	for(int i = T.head[u]; i ; i = T.nxt[i]){
		int v = T.to[i] ; 
		if(siz[v]) continue ;
		fa[v] = u ; 
		dfs1(v ,dp + 1) ; 
		siz[u] += siz[v] ; 
		if(siz[v] > maxson) son[u] = v , maxson = siz[v] ; 
	}
}
void dfs2(int u , int tp){
	top[u] = tp ;  
//	printf("u : %lld \n" , u) ; 
//	printf("u ; %lld tp : %lld \n" , u , tp) ; 
	if(son[u]) dfs2(son[u] , tp) ; 
	for(int i = T.head[u] ; i ; i = T.nxt[i]){
		int v = T.to[i] ;
//		printf(" u : %lld v : %lld \n" , u , v) ; 
		if(v == son[u] || v == fa[u]) continue ; 
		dfs2(v , v) ; 
	}
}
inline int query(int a , int b){
	while(top[a] != top[b]){
		if(dep[top[a]] < dep[top[b]]) swap(a , b) ; 
		a = fa[top[a]] ; 
	}
	return dep[a] < dep[b] ? a : b ; 
}
kkk(){
//	freopen("1.in" , "r" , stdin) ;
//	freopen("1.out" , "w" , stdout) ; 
	n =read() , m = read() ;
	tot = n ; 
	int u , v ; 
	for(int i = 1 ; i <= m ; i++){
		u = read() , v = read() ; 
		G.addedge(u , v) ; 
	}
	tarjan(1) ; 
	dfs1(1 , 1) ; 
	dfs2(1 , 1) ; 
	int lca ; 
	q = read() ; 
	while(q--){
		u = read() , v = read() ; 
		lca = query(u , v) ; 
//		printf("u : %lld dep : %lld v: %lld dep : %lld \n" , u ,dep[u] ,  v , dep[v]) ; 
//		printf("lca : %lld dep : %lld \n" , lca , dep[lca]) ;  
//		
		printf("%d\n" , (dep[u] + dep[v] - 2 * dep[lca])/2 + 1) ; 
	}
//	for(int i = 1 ; i <= tot ; i++){
//		printf("fa[%lld] :%d dep : %d top : %d \n" , i , fa[i] , dep[i] , top[i]) ; 
//	}
	return 0 ; 
}

2020/6/5 19:05
加载中...