Solution - CF555E Case of Computer Network

Posted on Edited on

CF555E Case of Computer Network

idea

边双缩点，LCA，树上差分。

解

步骤很多但代码很短的一道题。

首先，可以发现边双连通分量里面一定存在一种定向方式使得所有点可以互相到达。

那么直接边双缩点，然后你就得到了一个森林（因为环都被缩掉了）。

对于一组询问 (x,y)(x,y) ，如果 xx 和 yy 不在一颗树里面，那直接无解就行。

如果 xx 和 yy 在同一个点里面，直接过掉。

然后我们可以树上差分：搞两个数组，分别表示向上边和向下边。

先对每个询问都记录一下，然后 DfsDfs 一遍做个前缀和，如果某条边同时需要通过向上边和向下边，那就无解，否则有解。

CODE:

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
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e5+5,M=19;
int n,m,q;
int cnt1[N],cnt2[N];
struct Edge{ int pos,tag; };
vector<Edge> G[N];
vector<int> C[N];
int dfn[N],low[N],tot,st[N],top,col,num[N];
void Tarjan(int cur,int fe){
	dfn[cur]=low[cur]=++tot;
	st[++top]=cur;
	for (int i=0;i<(int)G[cur].size();++i){
		int to=G[cur][i].pos,tg=G[cur][i].tag;
		if (fe==tg) continue;
		if (!dfn[to]) Tarjan(to,tg),low[cur]=min(low[to],low[cur]);
		else low[cur]=min(dfn[to],low[cur]);
	}
	if (low[cur]==dfn[cur]){
		++col;
		while (st[top+1]!=cur) C[col].pb(st[top]),num[st[top--]]=col;
	}
}
int dep[N],fa[N][M+5],tr[N],tree;
void Dfsinit(int cur,int f){
	tr[cur]=tree;
	dep[cur]=dep[f]+1;
	fa[cur][0]=f;
	for (int i=1;i<=M;++i){
		if (dep[cur]>(1<<i)){
			fa[cur][i]=fa[fa[cur][i-1]][i-1];
		}else break;
	}
	for (int i=0;i<(int)C[cur].size();++i){
		int now=C[cur][i];
		for (int j=0;j<(int)G[now].size();++j){
			int to=num[G[now][j].pos];
			if (to==cur||dep[to]) continue;
			Dfsinit(to,cur);
		}
	}
}
inline int LCA(int x,int y){
	if (dep[x]<dep[y]) swap(x,y);
	for (int i=M;~i;--i){
		if (dep[x]-(1<<i)>=dep[y]) x=fa[x][i];
		if (x==y) return x;
	}
	for (int i=M;~i;--i){
		if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
	}
	return fa[x][0];
}
void Dfs(int cur,int f){
	for (int i=0;i<(int)C[cur].size();++i){
		int now=C[cur][i];
		for (int j=0;j<(int)G[now].size();++j){
			int to=num[G[now][j].pos];
			if (to==f||to==cur) continue;
			Dfs(to,cur);
			cnt1[cur]+=cnt1[to];
			cnt2[cur]+=cnt2[to];
		}
	}
	if (cnt1[cur]&&cnt2[cur]&&f){
		cout<<"No";
		exit(0);
	}
}
signed main(){
	cin>>n>>m>>q;
	for (int i=1;i<=m;++i){
		int x,y;cin>>x>>y;
		G[x].pb((Edge){y,i}),G[y].pb((Edge){x,i});
	}
	for (int i=1;i<=n;++i){
		if (!dfn[i]) Tarjan(i,0);
	}
	for (int i=1;i<=col;++i){
		if (!dep[i]) ++tree,Dfsinit(i,0);
	}
	for (int i=1;i<=q;++i){
		int x,y;cin>>x>>y;
		x=num[x],y=num[y];
		if (tr[x]!=tr[y]) return cout<<"No",0;
		if (x==y) continue;
		int lca=LCA(x,y);
		++cnt1[x],--cnt1[lca];
		++cnt2[y],--cnt2[lca];
	}
	for (int i=1;i<=col;++i){
		if (dep[i]==1) Dfs(i,0);
	}
	return cout<<"Yes",0;
}