刚学图论,样例都过不了,求助
查看原帖
刚学图论,样例都过不了,求助
261947
yama是女孩子楼主2021/2/7 20:16

RT

#include <cstdio>
#include <vector> 
#include <cstring>
using namespace std ;
const int MAXN = 2e5 + 10 ;
int n , m , q , fir[MAXN] , nxt[MAXN << 1] , to[MAXN << 1] , tot = 1 ;
vector <int> T[MAXN] ;
int dfn[MAXN] , low[MAXN] , cnt , vis[MAXN << 1] , cntc , col[MAXN] ; 
int f[MAXN] , g[MAXN] , vis_T[MAXN] , tot_T ;
int fa[MAXN][25] , dep[MAXN] ;
void add (int u , int v) {
	to[++tot] = v ;
	nxt[tot] = fir[u] ;
	fir[u] = tot ;
}
int min (int a , int b) {return a < b ? a : b ;}
void tarjan (int x , int fa) {
	dfn[x] = low[x] = ++cnt ;
	for (int i = fir[x] ; i ; i = nxt[i]) {
		if (i == fa) continue ;
		int v = to[i] ;
		if (!dfn[v]) {
			tarjan (v , i ^ 1) ;
			low[v] = min (low[v] , low[x]) ;
			if (low[v] > dfn[x]) vis[i] = vis[i ^ 1] = 1 ;
		}
		else low[x] = min (low[x] , dfn[v]) ;
	}
}
void dfs (int x) {
	col[x] = cntc ;
	for (int i = fir[x] ; i ; i = nxt[i]) {
		int v = to[i] ;
		if (vis[i] || col[v]) continue ;
		dfs (v) ;
	}
}
void dfs2 (int x) {
	dep[x] = dep[fa[x][0]] + 1 ;
	vis_T[x] = tot_T ;
	for (int i = 0 ; i < T[x].size () ; i++) {
		int v = T[x][i] ;
		if (v == fa[x][0]) continue ;
		fa[v][0] = x ;
		dfs2 (v) ;
	}
}
void swap (int &x , int &y) {
	x ^= y ^= x ^= y ;
}
int LCA (int x , int y) {
	if (dep[x] < dep[y]) swap (x , y) ; 
	for (int i = 20 ; i >= 0 ; i--)
		if (dep[fa[x][i]] >= dep[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] ;
}
bool check (int x) {
	for (int i = 0 ; i < T[x].size () ; i++) {
		int v = T[x][i] ;
		if (v == fa[x][0]) continue ;
		if (!check (v) || (f[v] && g[v])) return 0 ;
		f[x] += f[v] ; g[x] += g[v] ;
	}
	return 1 ;
}
int main () {
	scanf ("%d %d %d" , &n , &m , &q) ;
	for (int i = 1 ; i <= m ; i++) {
		int u , v ;
		scanf ("%d %d" , &u , &v) ;
		add (u , v) ; add (v , u) ; 
	}
	for (int i = 1 ; i <= n ; i++)
		if (!dfn[i]) tarjan (i , 0) ;
	for (int i = 1 ; i <= n ; i++)
		if (!col[i]) cntc++ , dfs (i) ;
	for (int i = 1 ; i <= n ; i++)
		for (int j = fir[i] ; j ; j = nxt[j]) {
			int v = to[j] ;
			if (col[i] < col[v]) {
				T[col[i]].push_back (col[v]) ;
				T[col[v]].push_back (col[i]) ;
			} 
		}
	for (int i = 1 ; i <= cntc ; i++)
		if (!vis_T[i]) tot_T++ , dfs2 (i) ; 
	for (int i = 1 ; i <= 20 ; i++)
		for (int j = 1 ; j <= cntc ; j++)
			fa[j][i] = fa[fa[j][i - 1]][i - 1] ;
	for (int i = 1 ; i <= q ; i++) {
		int x , y ;
		scanf ("%d %d" , &x , &y) ;
		x = col[x] ; y = col[y] ;
		if (vis_T[x] != vis_T[y]) return !printf ("No") ;
		int z = LCA (x , y) ;
		f[x]++ ; f[z]-- ;
		g[y]++ ; g[z]-- ;
	}
	for (int i = 1 ; i <= cntc ; i++)
		if (dep[i] == 1 && !check (i))
			return !printf ("No") ;
	printf ("Yes") ;
	return 0 ;
}
2021/2/7 20:16
加载中...