题解 [ARC092F] Two Faced Edges

· · 题解

link

题目大意

给一个 n 点 m 边的有向图。对于每一条边，查询取反其后图的 scc 数量是否改变。

n\leq10^3,m\leq 2×10^5

题解

首先我们给原图跑一边 tarjan 求出祂的 scc，对于边我们分情况讨论。

对于两端在同一个 scc 的边 (u,v)，改变 scc 数量意思是这条边反向会让这个 scc 变成多个 scc（祂不可能使 scc 增加）。减少的情况就是原本可以从 u 走到 v 但是现在不行，这种情况显然是 u\to v 只有只经过 (u,v) 的路径，u\to v 不存在除了 (u,v) 的其它路径。

对于两端不在同一个 scc 的边 (u,v)，改变 scc 数量的意思是这条边反向会使多个 scc 连成一个 scc（祂不可能使 scc 减少）。增加的情况就是 (v,u) 把 u,v 连在一个环里面，意思是 u\to v 存在除了 (u,v) 的其它路径。

可以发现，求 (u,v) 的答案，我们关心 ⌈ 原图中 u,v 所在 scc 是否相同 ⌋ 以及 ⌈ u\to v 有没有除了 (u,v) 的其它路径 ⌋，这两者异或即为答案。前者跑 tarjan 就很好求了，我们考虑后者怎么做。

只有 (u,v) 构成的路径显然长度为 1，除非重边，其它 u\to v 的路径长度都大于 1 呀！那我们就有一个不太成熟的想法，可不可以记录 f[u][v] 表示 u\to v 的最长路径长度呢（？我们会发现这玩意儿有点丑陋，我们想办法舍弃。

把 f 的定义舍弃最长，现在仅仅表示路径长度。我们肯定知道 ⌈ 暴力 dfs 不经过重复点 ⌋ 这种姿势算 f，是在图中抠出一颗搜索树算点到根的距离。那么这里 f[u,v] 算了什么，有两种可能性，走 u,v 或者走 u,t_0,...,v 算了距离！我们得固定一个 u 一次算祂的所有 f[u][i]，不然复杂度爆炸，于是乎我们不容易直接避免 (u,v) 的计算。

那我们怎么办呢，我们可以再搜一个数组 g[u][v]，祂与 f 的区别仅为搜索遍历边时顺序相反。如果 v 被搜，f 和 g 肯定一个先搜 v 一个先搜 t_0，搜了一个另一条边就不会进搜索树了。这样做我们可以利用 dfs 的小性质，如果 u\to v 的路径不仅仅只有 (u,v) 那么肯定会有 f[u][v]>1 或者 g[u][v]>1。这样就可以啦 qwq

下面是 chelsy 不知道可不可爱的代码（

#include<bits/stdc++.h>
#define pb push_back

using namespace std;

const int N=2e3, M=4e5;
int n, m, dfn[N], low[N], tim, u[M], v[M], cur[N];
int vis[N], stk[N], top, cnt, f[N][N], g[N][N];
vector<int> to[N];

void tarjan(int x) {
    dfn[x]=low[x]=++tim;
    vis[x]=1, stk[++top]=x;
    for(int i=0; i<to[x].size(); ++i) {
        int y=to[x][i];
        if(vis[y]==2) continue;
        if(!vis[y]) tarjan(y);
        low[x]=min(low[x],low[y]); 
    }
    if(dfn[x]==low[x]) {
        ++cnt; int p;
        while(stk[top+1]!=x) {
            p=stk[top--];
            cur[p]=cnt, vis[p]=2;
        }
    }
}

void dfs(int x,int p) {
    for(int i=0; i<to[x].size(); ++i) {
        int y=to[x][i];
        if(f[p][y]==-1) f[p][y]=f[p][x]+1, dfs(y,p);
    }
}

void dfs2(int x,int p) {
    for(int i=to[x].size()-1; i>=0; --i) {
        int y=to[x][i];
        if(g[p][y]==-1) g[p][y]=g[p][x]+1, dfs2(y,p);
    }
}

signed main() {
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; ++i) {
        scanf("%d%d", u+i, v+i);
        to[u[i]].pb(v[i]);
    }
    for(int i=1; i<=n; ++i) if(!vis[i]) tarjan(i);
    memset(f,-1,sizeof(f)), memset(g,-1,sizeof(g));
    for(int i=1; i<=n; ++i) f[i][i]=0, dfs(i,i);
    for(int i=1; i<=n; ++i) g[i][i]=0, dfs2(i,i);
    for(int i=1; i<=m; ++i) {
        bool t=(f[u[i]][v[i]]>1)|(g[u[i]][v[i]]>1);
        if(t^(cur[u[i]]==cur[v[i]])) printf("diff\n");
        else printf("same\n");
    }
    return 0;
}