P10572 [JRKSJ R8] +1-1 题解

发表于 分类于

题目思路

可以发现，非简单路径意味着可以走环，那么若是有两个相邻的点都是左括号或右括号，那么就可以反复走这两个点来刷左括号或右括号。同时，合法括号序列的长度必然为偶数，也就是说两点有合法路径时，必然有一条经过点数为偶数的路径。不妨假设询问路径为从\(x\)到\(y\)，那么当

  1. \(x\)有与其相连的左括号（称其为\(LL\)点对）
  2. \(y\)也有与其相连的右括号（称其为\(RR\)点对）
  3. 且\(LL\)点对到\(RR\)点对有偶数长度的路径

时，必然存在合法路径。

上面得出的结论是充分非必要条件，我们考虑怎么将其扩充为充分必要条件。我们发现，如果\(x\)与某一\(LL\)点对有路径，且到他们的路径之间构成的括号序列合法时，实际上等同于\(x\)就是\(LL\)点对的情况。对\(y\)点也类似，所以下面只对\(x\)分析。由于只要存在这样的\(LL\)就可以，所以我们只需要对\(x\)找到离他最近的的\(LL\)点对。对于最近的\(LL\)点对，显然只会构成\(()()\ldots()\)这样的括号序列（否则就不是最近了）。

对于这种最简单的括号序列，我们可以对原图的部分边的基础上建立一个二分图，只对相邻的左括号和右括号之间进行连边，显然这个二分图只会存在这种最简单的括号路径。这样只要判断\(x\)点是否和某一\(LL\)点对在这个二分图的同一连通块里就可以了。

现在我们解决了上面的条件1、2，考虑怎么转换原来的条件3并加以解决。原来条件3等效于\(LL\)由于\(x\)到\(LL\)的路径一定是偶数，\(y\)到\(RR\)的路径也是偶数，且\(x\)与\(y\)在同一连通块里，那么只需判断\(x\)到\(y\)是否具有偶数长度的路径。这里可以运用一个小Trick：

我们考虑尝试对原图的边直接构建二分图。在\(x\)与\(y\)在同一连通块的前提下，如果原图就是二分图，那么\(x\)与\(y\)存在偶数路径，当且仅当\(x\)与\(y\)在二分图的同一边；如果原图不是二分图，那么原图必然存在奇环，也就是必然存在偶数路径。

最后考虑一种特殊情况：\(x\)与\(y\)之间只存在\(()()\ldots()\)这样的路径，只要判断一下在上面的部分二分图上\(x\)与\(y\)是否在不同的两边且在这个二分图的同一连通块即可。

下面证明这几种情况的完备性。

如果存在一条合法路径，既不满足\(x\)与\(y\)能找到一条到\(LL\)或\(RR\)点对的路径，也不满足存在一条最简单的括号路径，那么这条路径上既不存在\(((\)和\())\)，也不存在简单的\(()\)，显然只能是空串。因此不存在这样的情况，完备性得证。

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
// #pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x & -x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
struct Graph
{
    vector<vector<int>> to;
    Graph() {}
    vector<int> vis;
    vector<int> col;
    Graph(int n)
    {
        to = vector<vector<int>>(n);
        vis = vector<int>(n);
        col = vector<int>(n);
    }
    bool checkBipartiteGraph(int x, int blocktype = 1, int fa = 0, int nowcol = 1)
    {
        vis[x] = nowcol;
        col[x] = blocktype;
        bool isBipart = true;
        for (auto y : to[x])
        {
            if (y == fa)
                continue;
            if (!vis[y])
                isBipart &= checkBipartiteGraph(y, blocktype, y, 3 - nowcol);
            else if (vis[y] == nowcol)
                isBipart = false;
        }
        return isBipart;
    }
    void fillCol(int x, int col = 4)
    {
        vis[x] = col;
        for (auto y : to[x])
        {
            if (vis[y] == col)
                continue;
            fillCol(y, col);
        }
    }
    void add(int x, int y)
    {
        to[x].push_back(y);
    }
};
string a;
void work()
{
    cin >> n >> m >> q;
    cin >> a;
    Graph fullGraph(n), withoutCommom_Graph(n);
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        if (a[x] != a[y])
        {
            withoutCommom_Graph.add(x, y);
            withoutCommom_Graph.add(y, x);
        }
        fullGraph.add(x, y);
        fullGraph.add(y, x);
    }
    int cnt1 = 0;
    for (int x = 0; x < n; x++)
    {
        if (fullGraph.vis[x] == 0)
        {
            cnt1++;
            if (fullGraph.checkBipartiteGraph(x, cnt1) == false)
                fullGraph.fillCol(x);
        }
    }
    int cnt2 = 0;
    for (int x = 0; x < n; x++)
        if (withoutCommom_Graph.vis[x] == 0)
            withoutCommom_Graph.checkBipartiteGraph(x, ++cnt2);
    vector<int> connectWithLL(n), connectWithRR(n);
    for (int x = 0; x < n; x++)
        for (auto y : fullGraph.to[x])
        {
            int blocktype = withoutCommom_Graph.col[x];
            if (a[x] == '(' && a[y] == '(')
                connectWithLL[blocktype] = 1;
            if (a[x] == ')' && a[y] == ')')
                connectWithRR[blocktype] = 1;
        }
    for (int t = 0; t < q; t++)
    {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        if (a[x] == a[y] || a[x] == ')')
        {
            cout << 0;
            continue;
        }
        int fullGraphCol_x = fullGraph.col[x], fullGraphCol_y = fullGraph.col[y];
        if (fullGraphCol_x != fullGraphCol_y)
        {
            cout << 0;
            continue;
        }
        int partGraphCol_x = withoutCommom_Graph.col[x], partGraphCol_y = withoutCommom_Graph.col[y];
        if (partGraphCol_x == partGraphCol_y)
        {
            cout << 1;
            continue;
        }
        else if (connectWithLL[partGraphCol_x] && connectWithRR[partGraphCol_y])
        {
            if (fullGraph.vis[x] != fullGraph.vis[y] || fullGraph.vis[x] == 4)
            {
                cout << 1;
                continue;
            }
            else
            {
                cout << 0;
                continue;
            }
        }
        else
        {
            cout << 0;
            continue;
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t-- > 0)
    {
        work();
    }
}