ac了 但是有疑问
by 星之哀伤 @ 2023-11-12 22:24:08
为什么缩点的时候用栈就能正确
深搜删割边就会wa后四个点
ac代码
```
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+1;
struct node{
int ne;
int bi;
};
int c[maxn],low[maxn],dfn[maxn],num,tot,dcc,d[maxn],f[maxn][22],ans[maxn],tt[maxn],cnt;
int n,m;
bool v[maxn];
vector<node> t[maxn];
vector<int> t1[maxn];
map<int,bool> vis[maxn];
queue<int> q;
stack<int>st;
/*void tarjan(int x,int fa){
dfn[x]=low[x]=++num;
//int flag=0;
for(int i=0;i<t[x].size();i++){
int y=t[x][i].ne;
if(!dfn[y]){
tarjan(y,x);
low[x]=min(low[x],low[y]);
if(low[y]>dfn[x]){
v[t[x][i].bi]=1;
}
/* if(low[y]>=dfn[x]){
flag++;
if(x!=root||flag>1) cut[x]=1;
}
}else if(y!=fa) low[x]=min(low[x],dfn[y]);
}
}
void dfs(int x){
c[x]=dcc;
for(int i=0;i<t[x].size();i++){
int y=t[x][i].ne;
if(c[y]||v[t[x][i].bi]) continue;
dfs(y);
}
}*/
void tarjan(int x,int fa) {
dfn[x] = low[x] = ++cnt;st.push(x);
for (int i = 0;i<t[x].size();i ++) {
int y = t[x][i].ne;
if (y == fa) continue;
if (!dfn[y]) {
tarjan(y,x);
low[x] = min(low[x],low[y]);
if (low[y] > dfn[x]) {
v[t[x][i].bi]=1;
}
} else {
low[x] = min(low[x],dfn[y]);
}
}
if (low[x] == dfn[x]) {
++num;c[x] = num;
while (st.top() != x) c[st.top()] = num,st.pop();
st.pop();
}
}
void bfs(){
q.push(1),d[1]=1;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<t1[x].size();i++){
int y=t1[x][i];
if(d[y]) continue;
d[y]=d[x]+1;
f[y][0]=x;
for(int j=1;j<=tot;j++){
f[y][j]=f[f[y][j-1]][j-1];
}
q.push(y);
}
}
}
int lca(int x,int y){
if(d[x]<d[y]) swap(x,y);
for(int i=tot;i>=0;i--) if(d[x]-(1<<i)>=d[y]) x=f[x][i];
if(x==y) return x;
for(int i=tot;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
void shuchu(int x)
{
int xx = 0;
for(; x; x>>=1)
{
xx++;
if(x & 1) tt[xx] = 1;
else tt[xx] = 0;
}
for (int i = xx; i >= 1; i-- ) printf("%d",tt[i]);
printf("\n");
}
int main(){
cin>>n>>m;
tot=log(n)/log(2)+1;
for(int a,b,i=1;i<=m;i++){
scanf("%d%d",&a,&b);
if(vis[a][b]==1) continue;
vis[a][b]=1,vis[b][a]=1;
node temp;
temp.ne=b,temp.bi=i;
t[a].push_back(temp);
node temp1;
temp1.ne=a,temp.bi=i;
t[b].push_back(temp1);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i,0);
}
/*for(int i=1;i<=n;i++){
if(!c[i]){
dcc++;
dfs(i);
}
}*/
for(int i=1;i<=n;i++){
for(int j=0;j<t[i].size();j++){
int x=t[i][j].ne;
if(c[x]==c[i]) continue;
t1[c[i]].push_back(c[x]);
//t1[c[i]].push_back(c[x]);
}
}
bfs();
int kk;
cin>>kk;
for(int a,b,i=1;i<=kk;i++){
cin>>a>>b;
int gg=d[c[a]]+d[c[b]]-2*d[lca(c[a],c[b])]+1;
shuchu(gg);
}
return 0;
}
```
by 星之哀伤 @ 2023-11-12 22:25:08