“蔚来杯“2022牛客暑期多校训练营3 F - Fief (点双连通算法)

57 阅读 0 评论 38 点赞

我是靠谱客的博主默默橘子，最近开发中收集的这篇文章主要介绍“蔚来杯“2022牛客暑期多校训练营3 F - Fief (点双连通算法)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

TP

题意大致就是保证形成的图连通且双连通分量形成一条链状，就是合法。
每次询问两点要注意特判两点是一个块中还是链的两端。

$C o d e :$

#include<bits/stdc++.h>
#include<unordered_map>
#define debug cout << "debug---
"
#define debug_ cout << "n---debug---n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, int> PII;
const int N = 1e5 + 10, M = 2e6 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;
int h[N], e[M], ne[M], idx;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfn[N], low[N], tim;
int root, stk[N], top, dcnt;
bool cut[N];
vector<int> dcc[N];
int fen[N], id[N];
//记录每个双连通分量内有多少个割点，特别的如果该点是割点则记录自己在多少个分量中
//记录每个点属于哪个分量
//只记录删掉某点后会形成的连通块数量是错的
//点双的图应该是一个个双连通分量由割点连接在一起
//当且仅当当前分量有三个及以上割点，或者某个割点连着三个及以上连通块
//是不合法的情况
void tarjan(int x) {
dfn[x] = low[x] = ++tim;
stk[++top] = x;
if (x == root && h[x] == -1) {
dcc[++dcnt].push_back(x);
return;
}
int cnt = 0;
for (int i = h[x]; ~i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[x] = min(low[x], low[j]);
if (dfn[x] <= low[j]) {
cnt++;
if (x != root || cnt > 1)cut[x] = true;
dcnt++;
int y;
do
{
y = stk[top--];
dcc[dcnt].push_back(y);
} while (y != j);
dcc[dcnt].push_back(x);//别忘记放割点
}
}
else low[x] = min(low[x], dfn[j]);
}
}
void solve() {
cin >> n >> m;
mem(h, -1);
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
int q; cin >> q;
if (n == 2) {
while (q--)cout << "YESn";
return;
}
int cnt = 0;
for (int i = 1; i <= n; i++)
if (!dfn[i]) {
root = i;
cnt++;
tarjan(i);
}
//图不连通肯定不合法
if (cnt > 1) {
while (q--)cout << "NOn";
return;
}
int num = dcnt;
for (int i = 1; i <= n; i++)
if (cut[i])id[i] = ++num;//对割点也给予一个连通块编号
for (int i = 1; i <= dcnt; i++)
for (int j = 0; j < sz(dcc[i]); j++) {
int v = dcc[i][j];
if (cut[v])fen[i]++, fen[id[v]]++;//所属连通块 以及 自身作为割点
else id[v] = i;//记录某点属于哪个连通块
}
for (int i = 1; i <= num; i++) {
if (fen[i] > 2) {
while (q--)cout << "NOn";
return;
}
}
while (q--)
{
int u, v;
cin >> u >> v;
u = id[u], v = id[v];
if (fen[u] == 0 && fen[v] == 0) {
//如果起点终点都在一个块中，无割点
cout << "YESn";
}
else if (fen[u] == 1 && fen[v] == 1 && u != v) {
//不在一个块就需要保证在链的两端，要特判 u != v
cout << "YESn";
}
else cout << "NOn";
}
}
int main() {
cinios;
int T = 1;
for (int t = 1; t <= T; t++) {
solve();
}
return 0;
}
/*
*/