开篇碎碎念
今天是继续图论的一天！所以就基环树启动！耶！！！下周就可以回家家啦，开心！！！
什么是基环树
简单来说就是一个树+一个环。在原本一棵树的基础上，添加了一个边，从而形成了一个环。
特殊的基环树
-
内向树：每个点仅有一个入边
-
外向树：每个点仅有一个出边
常见处理
- 化环为链 然后对于环进行计算
- 分类讨论 按照结果是否含有环
如何找环
拓扑排序：最后剩下的点都在环上
题目：P8943
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+10;
bool cir[MAXN];//是否在圆上
vector<int>e[MAXN];//存图
int tot[MAXN];//记录入边
int dir[MAXN];//环外到环的距离
int hdir[MAXN];//环上点的距离
int com[MAXN];//进入环的位置
int cnt=0;
int n;
void topu(){
queue<int>q;
for(int i=1;i<=n;i++){
if(tot[i]==1){
q.push(i);
}
}
int fr;
while(!q.empty()){
fr=q.front();
q.pop();
cir[fr]=0;
for(auto i:e[fr]){
if(cir[i]==0)continue;
tot[i]--;
if(tot[i]==1){
q.push(i);
}
}
}
}
int vis[MAXN];
void dfs(int x){//对环上的点标序号
hdir[x]=++cnt;
vis[x]=1;
for(auto i:e[x]){
if(!cir[i])continue;
if(vis[i])continue;
dfs(i);
}
}
void hdis(){//找出第一个在环上的点
int st;
for(int i=1;i<=n;i++){
if(cir[i]==1){
st=i;
break;
}
}
dfs(st);
}
int dis=0;
int viss[MAXN];
void dfss(int x,int w){
com[x]=w;
viss[x]=1;
for(auto i:e[x]){
if(cir[i])continue;
if(viss[i])continue;
dir[i]=dir[x]+1;
dfss(i,w);
}
}
void wdfs(){//找到所有在环上的点，遍历子树
for(int i=1;i<=n;i++){
if(cir[i]){
dis=0;
dfss(i,i);
}
}
}
int main(){
int q;
cin>>n>>q;
int u,v;
for(int i=1;i<=n;i++){
cir[i]=1;
}
for(int i=1;i<=n;i++){
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
tot[v]++;tot[u]++;
}
topu();
hdis();
wdfs();
while(q--){
cin>>u>>v;
int a1=dir[u];
int aw=com[u];
int b1=dir[v];
int bw=com[v];
if(hdir[aw]<hdir[bw])swap(aw,bw);
int dis=min(hdir[aw]-hdir[bw],cnt-hdir[aw]+hdir[bw]);
// cout<<a1<<' '<<aw<<' '<<b1<<' '<<bw<<' '<<dis<<endl;
if(dis+b1<=a1)cout<<"Deception"<<endl;
else cout<<"Survive"<<endl;
}
}