题目链接

好题！看视频！

分析

看了视频我们知道，只有我们缩完点之后是一条链，并且询问的两个的两个点是链的两个端点才YES；
那么首先无向图，我们求一下v-dcc缩点（点双）（acwing板子）；

下面讲一下求完 点双 之后的处理和细节！

一般思路：缩完点之后我们按照板子的思路开始建图（v-dcc和割点建边），然后判断是否是链；
仔细想想其实不用建图，直接记录一下度数就能判断链（注意这里v-dcc编号记得加上偏移量！）
缩完点之后，只有一个点直接满足；否则一定有两个点度数是1其它点度数是2才是链；
遍历的时候我们可以同时记录一下链的两个端点；

这里有个地方需要特别注意：
注意到一个割点的性质：一个割点一定至少属于两个v-dcc；
也就是说我们缩完点之后建的图中，割点一定不会出现在链的两个端点（两个端点一定是v-dcc编号）；
也就是说对于询问x y，如果x y任意一个是割点都不行，得特判掉，而且是一定得特判的！！！
为什么一定得特判？
还是那个性质：一个割点一定至少属于两个v-dcc；
那么如果此时x是割点，它对应的v-dcc的编号是有多个的，此时不特判就会造成混乱！

具体可以模拟一下这个样例：
5 6
1 2
1 3
2 3
3 4
3 5
4 5
1
3 5

答案：NO
不特判：YES

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
#include <random>
#include<bitset>
// #include 
#include<math.h>
#include<string.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"<<endl;
#define fi first
#define se second

#define ire(x) scanf("%d",&x)
#define iire(a,b) scanf("%d %d",&a,&b)
#define lre(x) scanf("%lld",&x)
#define llre(a,b) scanf("%lld %lld",&a,&b)
#define dre(x) scanf("%lf",&x)
#define ddre(a,b) scanf("%lf %lf",&a,&b)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl "\n"
#define PI acos(-1.0)
//#define int long long
// #define double long double
// typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<double, pair<int, double> > PDID;
typedef pair<char, char> PCC;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
typedef pair<int, pair<int, pair<int, int> > > PIIII;
typedef pair<ll, pair<int, int> > PLII;

const int maxn = 2e5 + 7;
const int N = 2e5;
const int M = 1e6 + 7;
const int mod = 998244353;
const int inv = mod - mod/2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}

int n,m;
int h[N],e[M],ne[M],idx;

int dfn[N],low[N],timestamp;    //时间戳
stack<int> st;  //栈

int vdcc_cnt;       //编号
vector<int> dcc[N]; //存一下每个双连通分量有哪些点
int id[N];	    //每个点属于哪个v-dcc

bool cut[N];    //标记每个点是否是割点
int root;       //全局根节点

int din[N*2];	//记录缩点后图中每个点的度数

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    st.push(u);

    if(u == root && h[u] == -1)     //特判一下孤立点
    {
        vdcc_cnt++;
        dcc[vdcc_cnt].push_back(u);
        id[u] = vdcc_cnt;
        return ;
    }

    int cnt = 0;    //记录当前子树有多少分支数
    for(int i=h[u];i!=-1;i=ne[i])
    {   
        int j = e[i];

        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u],low[j]);

            if(dfn[u] <= low[j])    //j走不到u上面，即把u删掉之后会多一个分支
            {
                cnt++;
                if(u!=root || cnt > 1) cut[u] = true;  //判断u是否是割点

                //下面把连通分量搞出来
                ++vdcc_cnt;
                int y;

                do
                {
                    y = st.top();
                    st.pop();
                    dcc[vdcc_cnt].push_back(y);
					id[y] = vdcc_cnt;
					
                }while(y != j);

                dcc[vdcc_cnt].push_back(u);
                id[u] = vdcc_cnt;
            }
        }
        else low[u] = min(low[u],dfn[j]);
    }
}

void solve()
{
	memset(h,-1,sizeof h);
	
	cin>>n>>m;
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	
	//求点双连通分量
	root = 1;
	tarjan(root);
	
	int flag = 1;
	rep(i,1,n) if(!dfn[i]) { flag = 0; break; }	//图不连通
	
	for(int i=1;i<=vdcc_cnt;i++)    //遍历每个v-dcc
        for(int j=0;j<dcc[i].size();j++)    //遍历该v-dcc所包含的点
            if(cut[dcc[i][j]])  //是割点
            {
            	din[dcc[i][j]] ++;  //记录度数
            	din[i+n] ++;	//记得加上偏移量
			}
	
	vector<int> lr;	//链的两个端点
	
	int cnt1 = 0;
	rep(i,1,n+vdcc_cnt) //遍历所有点的编号
		if(din[i] == 1) cnt1 ++, lr.push_back(i);
		else if(din[i] > 2) {flag = 0;break;}   //不是一条链
	
	if(!(cnt1 == 0 || cnt1 == 2)) flag = 0; //不是一条链
	
	int q;
	cin>>q;
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		
		if(!flag || cut[x] || cut[y])   //flag不满足 || x y是割点
		{
			cout<<"NO\n";
			continue;
		}
		if(cnt1 == 0)   //只有一个v-dcc的时候直接满足
		{
			cout<<"YES\n";
			continue;
		}
		
		x = id[x] + n;	//属于哪个v-dcc（记得加上偏移量）
		y = id[y] + n;
		
		if((x == lr[0] && y == lr[1]) || (x == lr[1] && y == lr[0])) cout<<"YES\n";
		else cout<<"NO\n";
	}
}

int main()
{
	IOS;
	
	int t;
//	ire(t);
//	cin>>t;
	t = 1;
	while(t--)
	{
		solve();
	}
	
 	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
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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214