[图论记录]AT3945 [ARC092D] Two Faced Edges

**题意** ： 给出一张 $n$ 个点 $m$ 条边的有向图，保证不存在重边和自环。 对于每条边，判断将其反向后（其他边不变），图中强连通分量的数量是否改变。 $n\leq 10^3,m\leq 2\times 10^5$ ，时限$\texttt{5s}$。 ------------ 对于边 $u\rightarrow v$ ，若将其反向: - 若 $u,v$ 在同一个强连通分量内。 强连通分量个数不可能增加，但该强连通分量可能被破坏。 若图中存在一条 $u\rightarrow v$ 的路径，且不含该边，则不会破坏，反之则会。 - 若 $u,v$ 不在同一个强连通分量内。 若图中存在一条 $u\rightarrow v$ 的路径，且不含该边，则会增加一个强连通分量，反之无变化。 记 $f(u,v)$ 表示“$u,v$ 在同一个强连通分量内”， $g(u,v)$ 表示图中存在 $u\rightarrow v$ 的路径，且不含边 $u\rightarrow v$。 综上所述，只有 $f(u,v),g(u,v)$ 两者之一成立，才会有贡献。 $f$ 容易用 $\rm Tarjan$ 缩强连通分量预处理。 接下来要对每条边求出 $g(u,v)$。 - $O(nm)$ 做法 考虑对于每个 $u$ 分别求出 $g(u,\_)$。 从 $u$ 开始 $\rm dfs$ ，反转边表再次 $\rm dfs$。 若点 $v$ 在两个 $\rm dfs$ 树中深度均为 $1$ ，则说明 $u\rightarrow v$ 是必经边，否则不是。 - $O(n^3/w+m)$ 做法 仍然考虑对于每个 $u$ 分别求出 $g(u,\_)$。 对于某个 $i\neq u$ ， $g(u,i)=1$ 当且仅当存在 $j\neq i,u$ ，满足存在简单路径 $u\rightarrow j⇝i$。 将 $u$ 点删除，将所有直接与 $u$ 相连的点记为 $v_1,v_2,...,v_k$。 顺次考虑 $i=1\sim k$ ，从 $v_i$ 开始搜索（不重复遍历之前搜过的点），所有搜到的点 $t$（除了 $v_i$ 本身）都能满足 $g(u,t)=1$。 （这里用 $\rm bfs$ 常数较小） 为了处理 $u\rightarrow v_j⇝v_i\ (i<j)$ 的情况，还需反过来再跑一次。 这样的搜索复杂度是 $O(n+m)$ 的，瓶颈在于，无论目的地是否被标记过，我们都要再次检查出边。 考虑利用 `bitset` 进行优化，记目前还未发现 $g(u,t)=1$ 的 $t$ 的集合为 $S$ ，点 $u$ 的出边的集合为 $G_u$ 。我们搜索时，只需考虑集合 $S∩G_u$ 内的元素。 下面的代码段可以用 $O\big(|T|n/w\big)$ 的代价找出 `bitset` $T$ 内的所有元素。 ```cpp for(int i=T._Find_first();i!=T.size();i=T._Find_next(i)) ``` 每个点只会被搜索到一次，故复杂度为 $O(n^2/w)$。 ```cpp #pragma GCC optimize(3) #include<algorithm> #include<cstdio> #include<vector> #include<bitset> #include<queue> #define pb push_back #define MaxN 1003 using namespace std; vector<int> g[MaxN],p[MaxN]; int dfn[MaxN],low[MaxN],tim,stk[MaxN],top,col[MaxN],Bcnt; void tar(int u) { stk[++top]=u; low[u]=dfn[u]=++tim; for (int i=0,v;i<g[u].size();i++) if (!dfn[v=g[u][i]]) {tar(v);low[u]=min(low[u],low[v]);} else if (!col[v])low[u]=min(low[u],dfn[v]); if (low[u]==dfn[u]){ Bcnt++; while(stk[top+1]!=u) col[stk[top--]]=Bcnt; } } bool vis[MaxN]; bitset<MaxN> t[MaxN],now,sav; queue<int> q; void bfs(int st) { q.push(st); while(!q.empty()){ int u=q.front();q.pop(); sav=t[u]&now; for (int i=sav._Find_first();i!=sav.size();i=sav._Find_next(i)) {now[i]=0;q.push(i);} } } bool ans[200500]; int n,m; int main() { scanf("%d%d",&n,&m); for (int i=1,u,v;i<=m;i++){ scanf("%d%d",&u,&v); g[u].pb(v);p[u].pb(i); t[u][v]=1; } for (int i=1;i<=n;i++) if (!dfn[i])tar(i); for (int u=1;u<=n;u++){ if (g[u].size()<=1)continue; now.set();now[u]=0; for (int i=0,v;i<g[u].size();i++) if (now[v=g[u][i]])bfs(v); else ans[p[u][i]]=1; now.set();now[u]=0; for (int i=0,v;i<g[u].size();i++) if (ans[p[u][i]])now[g[u][i]]=0; for (int i=(int)g[u].size()-1,v;i>=0;i--) if (now[v=g[u][i]]||ans[p[u][i]])bfs(v); else ans[p[u][i]]|=1; } for (int u=1;u<=n;u++) for (int i=0;i<g[u].size();i++) ans[p[u][i]]^=(col[u]==col[g[u][i]]); for (int i=1;i<=m;i++) puts(ans[i] ? "diff" : "same"); return 0; } ```