“蔚来杯“2022牛客暑期多校训练营3，签到题CAJHF
题号 标题 已通过代码 通过率 团队的状态
A Ancestor 点击查看 1383/3940
B Boss 点击查看 54/734
C Concatenation 点击查看 2603/9404
D Directed 点击查看 62/157
E Electrician 点击查看 18/38
F Fief 点击查看 378/2528
G Geometry 点击查看 73/1076
H Hacker 点击查看 468/3315
I Ice Drinking 点击查看 28/212
J Journey 点击查看 1236/7800
C.Concatenation
链接：https://ac.nowcoder.com/acm/contest/33188/C
来源：牛客网
题目描述
NIO was the king of the OIN Kingdom.
He had NN children and wanted to teach them how to count. In the OIN Kingdom, pental is used in counting, so his children can only use 0, 1, 2, 3, and 4 to represent a number.
One day, NIO asked his children to write down their favorite numbers. After that, he came out with a problem: if he concatenated these numbers into a big number, what is the smallest number he could get? However, this problem was too hard for him to solve, so can you help him?
输入描述:
The first line contains an integer N(1 \le N \le 2*10^6)N(1≤N≤2∗10
6
), denoting the number of NIO’s children.
Then follows NN lines, each line contains a string s_is
i
denotes the favorite number of the iith child. The string is composed of 0, 1, 2, 3, and 4, but may have leading zeros because NIO’s children hadn’t fully understood how to count.
\sum_{i=1}^{N} |s_i|\le 2*10^7∑
i=1
N
∣s
i
∣≤2∗10
7
输出描述:
One integer denotes the smallest number NIO can get.
示例1
输入
复制
5
121
1
12
00
101
输出
复制
00101112112
备注:
If you have designed an algorithm whose time complexity is O(|S|\log|S|)O(∣S∣log∣S∣) or so, please think twice before submitting it. Any algorithm other than linear complexity is NOT supposed to pass this problem. But of course, you can have a try. If you do so, we wish you good luck.
题意：
- 给定n个字符串，求一个将他们拼接起来的方案，使得结果的字典序最小。
思路：
- 一个简单的做法是，对n个字符串排序，a在b前面的条件是a+b<b+a。
- 使用stable_sort可以保证复杂度为O(|S|log n)。
- 为了优化速度，还可以给cmp函数加上&，const，和inline。
- 可以换int为LL，然后把变量开到外面去。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
const LL maxn = 4e6+10;
string a[maxn];
inline bool cmp(const string &x,const string &y){
return x+y<y+x;
}
int main(){
IOS;
LL n; cin>>n;
for(LL i = 1; i <= n; i++){
cin>>a[i];
}
sort(a+1,a+n+1,cmp);
for(LL i = 1; i <= n; i++){
cout<<a[i];
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
A.Ancestor
链接：https://ac.nowcoder.com/acm/contest/33188/A
来源：牛客网
题目描述
NIO is playing a game about trees.
The game has two trees A, BA,B each with NN vertices. The vertices in each tree are numbered from 11 to NN and the ii-th vertex has the weight v_iv
i
. The root of each tree is vertex 1. Given KK key numbers x_1,\dots,x_kx
1
,…,x
k
, find the number of solutions that remove exactly one number so that the weight of the lowest common ancestor of the vertices in A with the remaining key numbers is greater than the weight of the lowest common ancestor of the vertices in B with the remaining key numbers.
输入描述:
The first line has two positive integers N,K (2 \leq K \leq N \leq 10^5)N,K(2≤K≤N≤10
5
).
The second line has KK unique positive integers x_1,\dots,x_K (x_i \leq N)x
1
,…,x
K
(x
i
≤N).
The third line has NN positive integers a_i (a_i \leq 10^9)a
i
(a
i
≤10
9
) represents the weight of vertices in A.
The fourth line has N - 1N−1 positive integers {pa_i}{pa
i
}, indicating that the number of the father of vertices i+1i+1 in tree A is pa_ipa
i
.
The fifth line has nn positive integers b_i (b_i \leq 10^9)b
i
(b
i
≤10
9
) represents the weight of vertices in B.
The sixth line has N - 1N−1 positive integers {pb_i}{pb
i
}, indicating that the number of the father of vertices i+1i+1 in tree B is pb_ipb
i
.
输出描述:
One integer indicating the answer.
示例1
输入
复制
5 3
5 4 3
6 6 3 4 6
1 2 2 4
7 4 5 7 7
1 1 3 2
输出
复制
1
说明
In first case, the key numbers are 5,4,3.
Remove key number 5, the lowest common ancestors of the vertices in A with the remaining key numbers is 2, in B is 3.
Remove key number 4, the lowest common ancestors of the vertices in A with the remaining key numbers is 2, in B is 1.
Remove key number 3, the lowest common ancestors of the vertices in A with the remaining key numbers is 4, in B is 1.
Only remove key number 5 satisfies the requirement.
示例2
输入
复制
10 3
10 9 8
8 9 9 2 7 9 0 0 7 4
1 1 2 4 3 4 2 4 7
7 7 2 3 4 5 6 1 5 3
1 1 3 1 2 4 7 3 5
输出
复制
2
备注:
The lowest common ancestor (LCA) (also called least common ancestor) of two nodes v and w in a tree or directed acyclic graph (DAG) T is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).(From Wiki.)
题意：
- 给出两棵编号1-n的树A B，A B树上每个节点均有一个权值，给出k个关键点的编号𝑥_1…𝑥_𝑛，问有多少种方案使得去掉恰好一个关键点使得剩余关键点在树A上LCA的权值大于树B上LCA的权值。
思路：
- 预处理出关键点序列的在树A B上的前缀LCA和后缀LCA，枚举去掉的关键节点并使用前后缀LCA算出剩余节点的LCA比较权值即可。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
const int maxn = 1e5+10;
int n, k;
int va[maxn], vb[maxn], x[maxn];
struct tree{
vector<int>G[maxn];
int fa[maxn], siz[maxn], son[maxn], top[maxn], dep[maxn];
int pre[maxn], lst[maxn];
void add(int x, int y){
G[x].push_back(y);
}
void dfs(int x){
siz[x] = 1;
for(int y : G[x]){
fa[y] = x;
dep[y] = dep[x]+1;
dfs(y);
if(siz[y] > siz[son[x]])son[x] = y;//x的重儿子
siz[x] += siz[y];
}
}
void dfs(int x, int y){ //轻重链剖分
top[x] = y; //所在链链顶
if(son[x])dfs(son[x], y); //重链往下去不用更新链顶
for(int y : G[x]){
if(y==son[x])continue;
dfs(y,y); //更新y为链顶
}
}
//LCA复杂度：暴力O(n), 倍增O(logn~nlogn), TarjianO(logn~n), 树剖O(logn)
int lca(int x, int y){
while(top[x] != top[y]){//不在同一条链上 每次链顶深度较大的点往上爬
if(dep[top[x]] < dep[top[y]])swap(x,y);
x = fa[top[x]]; //进入新的链
}
if(dep[x] < dep[y])return x;//进入同一条链上时, 深度小的点在前面
return y;
}
void do_lca(){
dfs(1);
dfs(1,-1);
pre[1] = x[1];
for(int i = 2; i <= k; i++){
pre[i] = lca(pre[i-1], x[i]);
}
lst[k] = x[k];
for(int i = k-1; i; i--){
lst[i] = lca(lst[i+1], x[i]);
}
}
int get_lca(int i){
if(i==1)return lst[2];
if(i==k)return pre[k-1];
return lca(pre[i-1], lst[i+1]);
}
}treea, treeb;
int main(){
//input
IOS;
cin>>n>>k;
for(int i = 1; i <= k; i++)cin>>x[i];
for(int i = 1; i <= n; i++)cin>>va[i];
for(int i = 2; i <= n; i++){
int t; cin>>t; treea.add(t,i); //t->i
}
for(int i = 1; i <= n; i++)cin>>vb[i];
for(int i = 2; i <= n; i++){
int t; cin>>t; treeb.add(t,i);
}
//求所有关键点的前缀,后缀lca
treea.do_lca(); treeb.do_lca();
//枚举去掉的关键点
int ans = 0;
for(int i = 1; i <= n; i++){
int la = treea.get_lca(i); //去掉i后a的lca
int lb = treeb.get_lca(i); //去掉i后b的lca
if(va[la] > vb[lb])ans++;
}
cout<<ans<<"\n";
return 0;
}
- 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
J.Journey
链接：https://ac.nowcoder.com/acm/contest/33188/J
来源：牛客网
题目描述
NIO and Desprado2 are good friends and they lives in the same city. However, everytime NIO drive to visit desprado2, it takes him a long time to wait for red lights, and NIO is very distressed about this. There are nn crossroads in their city. NIO is a very unlucky guy, everytime he go straight, turn left or turn around at a crossroad, he will encounter a red light and have to wait for it. Turning right at a crossroad don’t need to wait for the red light.
NIO hates red lights, so he wants to know the minimal number of red lights he would encounter. Can you help him?
输入描述:
The first line contains an integer nn, 2\le n\le 5000002≤n≤500000, denotes the number of crossroads in the city.
Then follows nn lines, each line contains four distinct integers c_{i,1}c
i,1
, c_{i,2}c
i,2
, c_{i,3}c
i,3
, c_{i,4}c
i,4
(0\le c_{i,j}\le n0≤c
i,j
≤n), which denotes the starting points of the four roads to the iith crossroad. If c_{i,j}=0c
i,j
=0, then this roads are from some other city and NIO will never go this way. The roads are in counter-clockwise order, that is, if NIO are at road <c_{i,j}, ic
i,j
,i> and wants to go to road <i, c_{i,j%4+1}i,c
i,j%4+1
, he don’t need to wait for the red light because he is turning right at crossroad ii, otherwise he will have to wait the red light. It is guaranteed that the map doesn’t contain multiple edges and self-loops. It is also guaranteed that all the roads are bi-directional.
The last line contains four integers s_1s
1
, s_2s
2
, t_1t
1
, t_2t
2
(1\le s_1,\ s_2,\ t_1,\ t_2\le n1≤s
1
, s
2
, t
1
, t
2
≤n). NIO is at the road <s_1,s_2s
1
,s
2
and he wants to go to road <t_1,t_2t
1
,t
2
and visit Desprado2. It is guaranteed that both roads are in the map given above.
Please note that road <a,ba,b> is not equivalent to road <b,ab,a>. If NIO is at road <a,ba,b> and he wants to go to road <b,ab,a>, he should turn around at crossroad b and wait for a red light.
输出描述:
Output one integer, the minimal number of red lights NIO would encounter.
If there is no way to visit Desprado2, print -1 instead.
示例1
输入
复制
4
3 4 0 0
0 0 4 3
2 1 0 0
2 0 0 1
4 2 4 1
输出
复制
1
说明
One of the optimal route is: turn right at crossroad 2, turn right at crossroad 3, turn right at crossroad 1, and turn around at crossroad 4.
The picture is as follows:
题意：
- 给定一个城市有n个十字路口，除了右转，都需要等红灯，直行、左转和掉头都需要，求起点到终点最少等几次红灯。
思路：
- 把每条路看做点，十字路口处连边，形成一个边权为0/1的有向图。最简单的做法是dijkstra求最短路。也可以用BFS解决，注意用一个deque维护队列。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e6+10;
struct node{ int x, fx; }; //十字路口，方向
int c[maxn][5], dist[maxn][5]; //站在路口x，方向i时的最小时间
int main(){
int n; cin>>n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= 4; j++)
cin>>c[i][j]; //每个道路点有4条边
int s1, s2, t1, t2; cin>>s1>>s2>>t1>>t2;
//bfs
memset(dist,-1,sizeof(dist));
queue<node>q;
for(int i = 1; i <= 4; i++){
if(c[s2][i]==s1){
dist[s2][i] = 0; q.push({s2,i}); break;
}
}
while(q.size()){
node t = q.front(); q.pop();
for(int i = 1; i <= 4; i++){
int nt = c[t.x][i]; //四条边能到的点
if(nt==0)continue; //无法联通
int j;
for(j = 1; j <= 4; j++){
if(c[nt][j] == t.x)break;//j方向是往回走的
}
int w = 1; //边权
if(i==t.fx%4+1)w = 0; //右转不用边权
if(dist[t.x][t.fx]+w < dist[nt][j] || dist[nt][j]==-1){
dist[nt][j] = dist[t.x][t.fx]+w;
q.push({nt,j});
}
}
}
//ans
int ans = 0;
for(int i = 1; i <= 4; i++){
if(c[t2][i]==t1)ans = dist[t2][i];
}
cout<<ans<<"\n";
return 0;
}
- 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
H.Hacker
链接：https://ac.nowcoder.com/acm/contest/33188/H
来源：牛客网
题目描述
NIO is a hacker who likes to crack passwords for fun.
But one day he forgot his password. He quickly listed some vague clues. There is a lowercase string AA of length nn and kk lowercase strings B_1,\dots,B_kB
1
,…,B
k
of length mm. Given a uniform weight v_1, \dots, v_mv
1
,…,v
m
represents the weight of each position of any B_iB
i
.
To figure out his password, for all B_iB
i
, he wants to find its maximum interval weight sum, and the string formed by this interval is a substring of AA(An empty interval represents an empty string, which is legal).
输入描述:
The first line contains three positive integers n, m, k (n,m,k \leq 10^5, m * k \leq 10^6)n,m,k(n,m,k≤10
5
,m∗k≤10
6
).
The second line contains a string AA of length nn.
The third line contains mm integers v_i (-10^9 \leq v_i \leq 10^9)v
i
(−10
9
≤v
i
≤10
9
).
The next kk lines represent the string {B_i}{B
i
}.
输出描述:
kk lines for kk answers.
示例1
输入
复制
5 5 5
uqusa
-9 -7 8 -8 -3
saimh
qusam
qusaf
ubgxj
uquxw
输出
复制
0
8
8
0
8
示例2
输入
复制
10 8 5
aepeihmkkz
0 -3 2 -4 -5 2 -5 5
epesxnud
epeihmkk
peihmrgo
epeihqvy
eppjkuaz
输出
复制
2
5
2
2
5
说明
For B_1B
1
, the interval [3,3] forms the string ‘e’ is a substring of AA and the interval sum is 2. Although the interval [1,3] forms the string ‘epe’ is also a substring of AA, but the interval sum is -1 less than 2.
题意：
- 给出长度为n的小写字符串A和k个长度为m的小写字符串𝐵_1…𝐵_𝑘，𝐵的每个位置拥有统一的权值𝑣_1…𝑣_𝑚
- 对于每个𝐵_𝑖求最大和区间满足该区间构成的字符串是A的子串（空区间合法）。
思路：
- 我们可以将问题进行转化，相当于对𝐵_𝑖的每个位置求出它作为结束位置在A中的最长子串长度，然后在该区间求最大子段和，所有位置的最大值即为答案。
- 对于每个位置的最长子串，可以对A建后缀自动机，然后𝐵_𝑖从左往右在A的后缀自动机上转移，如果当前节点无法转移跳至父亲节点，最后无法转移则长度为0，转移成功则为转移前节点的最大长度+1。
- 后缀自动机学习资料：
https://oi-wiki.org/string/sam/
https://www.luogu.com.cn/blog/Kesdiael3/hou-zhui-zi-dong-ji-yang-xie
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
struct SuffixAutomaton { //板子
static constexpr int ALPHABET_SIZE = 26, N = 1e5;
struct Node {
int len;
int link;
int next[ALPHABET_SIZE];
Node() : len(0), link(0), next{} {}
} t[2 * N];
int cntNodes;
SuffixAutomaton() {
cntNodes = 1;
std::fill(t[0].next, t[0].next + ALPHABET_SIZE, 1);
t[0].len = -1;
}
int extend(int p, int c) {
if (t[p].next[c]) {
int q = t[p].next[c];
if (t[q].len == t[p].len + 1)
return q;
int r = ++cntNodes;
t[r].len = t[p].len + 1;
t[r].link = t[q].link;
std::copy(t[q].next, t[q].next + ALPHABET_SIZE, t[r].next);
t[q].link = r;
while (t[p].next[c] == q) {
t[p].next[c] = r;
p = t[p].link;
}
return r;
}
int cur = ++cntNodes;
t[cur].len = t[p].len + 1;
while (!t[p].next[c]) {
t[p].next[c] = cur;
p = t[p].link;
}
t[cur].link = extend(p, c);
return cur;
}
};
const int maxn =2e5+10;
LL w[maxn], s[maxn];
int main(){
IOS;
int n, m, k; cin>>n>>m>>k;
string a; cin>>a;
int p = 1;
SuffixAutomaton sam;
for(char ch : a){
p = sam.extend(p, ch-'a');
}
for(int i = 0; i < m; i++)cin>>w[i];
for(int i = 0; i < m; i++)s[i+1] = s[i]+w[i];
while(k--){
string b; cin>>b;
int p = 1;
LL ans = 0;
deque<int>q{0};
for(int i = 0, j = 0, len = 0; i < m; i++){
while(j < m && sam.t[p].next[b[j]-'a']){
p = sam.t[p].next[b[j]-'a'];
len++;
j++;
while(q.size() && s[j]>s[q.back()]){
q.pop_back();
}
q.push_back(j);
}
while(q.front() < i)q.pop_front();
ans = max(ans, s[q.front()]-s[i]);
len--;
if(len <= sam.t[sam.t[p].link].len){
p = sam.t[p].link;
}
}
cout<<ans<<"\n";
}
return 0;
}
- 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
F.Fief
链接：https://ac.nowcoder.com/acm/contest/33188/F
来源：牛客网
题目描述
Duke NIO had 2 sons, Antileaf and Fstqwq, and they would inherit Duke NIO’s fief. Duke NIO’s fief was composed of nn cities, and there were mm bi-direction roads connecting these cities. For fairness, Duke NIO made the following rules for Antileaf and Fstqwq when inheriting his fief:
Firstly, both Antileaf and Fstqwq could choose a favorite city.
Then, according to the two favorite cities, Duke NIO would make a list. The content of the list is his n cities, and the first item of the list is Antileaf’s favorite city while the last item of the list is Fstqwq’s favorite city.
After that, Antileaf and Fstqwq could begin to inherit his fief. The number of cities each one would get should be determined by drawing a lot. For instance, Antileaf would get the first aa cities in NIO’s list (aa is uniformly random between 11 and n-1n−1) while Fstqwq would get the last n-an−a cities.
After all the cities were assigned to his two sons, each son’s fief should be a connected component.
However, he found that in some cases, he couldn’t find a list that meet his requirement. He came out with some questions - if Antileaf chose city xx as his favorite city and Fstqwq chose city yy, could he always find a list such that Antileaf and Fstqwq’s fief would be always connected regardless of the result of the lottery?
输入描述:
The first line contains two integers nn and mm (2\le n\le 1000002≤n≤100000, 0\le m\le 2000000≤m≤200000), denoting the number of cities and the number of roads. Then follows mm lines, each line contains two integers u_iu
i
and v_iv
i
(1\le u_i,\ v_i\le n1≤u
i
, v
i
≤n, u_i\ne v_iu
i
=v
i
), denotes the roads.
After that follows a line with a single integer qq (1\le q\le 1000001≤q≤100000), which denotes the number of NIO’s queries. And then follows qq lines, each line contains two integers x_ix
i
and y_iy
i
(1\le x_i,\ y_i\le n1≤x
i
, y
i
≤n, x_i\ne y_ix
i
=y
i
), the meaning is described above.
输出描述:
Output qq lines. For the ii-th line, if the answer of the ii-th query is true, print “YES” (excluding quotes), otherwise print “NO” (excluding quotes).
示例1
输入
复制
4 3
1 2
2 3
4 3
3
1 3
4 1
3 4
输出
复制
NO
YES
NO
说明
For the second query, the only valid list is [4, 3, 2, 1][4,3,2,1]
示例2
输入
复制
4 6
1 2
1 3
1 4
2 3
2 4
3 4
2
1 4
2 4
输出
复制
YES
YES
说明
For the first query, one of the valid list is [1, 3, 2, 4][1,3,2,4].
For the second query, one of the valid list is [2, 3, 1, 4][2,3,1,4].
备注:
For the second query in the first example, the only valid list is (4, 3, 2, 1)(4,3,2,1).
For the first query in the second example, one valid list is (1, 3, 2, 4)(1,3,2,4).
For the second query in the second example, one valid list is (2, 3, 1, 4)(2,3,1,4).
题意：
- 给定一个无向图，每次询问两点x, y，求是否存在一个n的排列，使得第一个元素为x，最后一个元素为y，且排列的任意一个前缀、任意一个后缀都连通。
思路：
- 该题意等价于询问是否存在一个以x、y为极点的双极定向。双极定向存在，当且仅当添加一条边(x, y)以后图是点双联通的。关于图的双极定向问题，可以自行查找资料了解。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, m; cin>>n>>m;
vector<vector<int> >G(n);
for(int i = 0; i < m; i++){
int u, v; cin>>u>>v;
u--; v--;
G[u].push_back(v);
G[v].push_back(u);
}
//e-dcc边双联通: 不管删除掉哪一条边整个图都是连通的
//v-dcc点双联通: 不管删除掉哪一个点整个图都是连通的
//tarjan求 无向图-点双连通分量
//dfn: x节点是第几个被遍历到的
//low: 包含x在内的强连通分量的dfn的最小值（也就是说这个强连通分量中最早被遍历到的）
//stk: 用一个栈stack来存储遍历到的点
//e : 用于存储找到的强连通分量
vector<int>dfn(n,-1), low(n);
vector<int>stk;
vector<vector<int>>e(n);
int cur = 0, cnt = n;
function<void(int)>dfs = [&](int u){
dfn[u] = low[u] = cur++;
stk.push_back(u);
for(auto v : G[u]){
//对于每一个当前节点的子节点，如果之前没有遍历到，就往下遍历
if(dfn[v] == -1){
dfs(v);
low[u] = min(low[u], low[v]);//并在遍历后取low的min值
//如果当前节点的dfn的值等于low的值,由于low表示包含当前节点的强连通分量的最小dfn的值
//那么我们就可以认为low被传递了一圈又回到了当前dfn，也就代表找到了一个强联通分量，
//对于根节点来说, 这个是必然满足的 把所有以u为根节点的子连通块全部存下来
//不能不通过这个点到u的祖先节点, 则u就是这个连通分量的割点
if(low[v] == dfn[u]){
//那么我们就把从当前的栈顶一直到当前元素的栈中元素全部弹出并作为强联通分量的一部分
e.push_back({});
int x;
do{
x = stk.back();
e[cnt].push_back(x);
e[x].push_back(cnt);
stk.pop_back();
}while(x != v);
e[cnt].push_back(u);
e[u].push_back(cnt);
cnt++;
}
}else{
//如果之前已经遍历到，且是栈中元素, 我们直接传递dfn的值
//无需vis判重数组的原因: 由于在有向图的强连通分量中, u能走到的点, 不一定是属于该SCC(因为该点不一定就能到u),
//只有在栈中的才属于, 而无向图能走到的点就一定属于当前连通块
low[u] = min(low[u], dfn[v]);
}
}
};
dfs(0);
int q; cin>>q;
if(count(dfn.begin(),dfn.end(),-1)){
while(q--)cout<<"NO\n"; return 0;
}
if(cnt == n+1){ //点双联通
while(q--)cout<<"YES\n"; return 0;
}
vector<int>deg(n);
int ok = 1;
for(int i = 0; i < n;i++){
for(int j : e[i])deg[i] += j>=n;
if(deg[i] > 2)ok = 0;
}
vector<int>end;
for(int i = n; i < cnt; i++){
int c = 0;
for(int j : e[i]){
c += deg[j] > 1;
}
if(c > 2)ok = 0;
if(c == 1)end.push_back(i);
}
if(!ok){
while(q--)cout<<"NO\n"; return 0;
}
vector<int>a(n);
for(int i = 0; i < 2; i++){
for(int j : e[end[i]]){
if(deg[j] == 1){
a[j] = 1<<i;
}
}
}
while(q--){
int x, y; cin>>x>>y;
x--; y--;
if((a[x] | a[y]) == 3)cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
- 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
- 97
- 98
- 99
- 100
- 101
- 102
文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。
原文链接：gwj1314.blog.csdn.net/article/details/126013044
- 点赞
- 收藏
- 关注作者
评论（0）