题解 AT3945 【[ARC092D] Two Faced Edges】
CYJian
2020-02-28 23:17:16
考虑翻转 $u \rightarrow v$ 这条边对于强连通分量数量的影响，只需要考虑下面两个因素就行了：
1. 原图中存在一条 $v \rightarrow u$ 的路径。
2. 原图中存在一条 $u \rightarrow v$ 的路径，且不含上面的那条边。
若上述两个因素中有且仅有一个满足，则强连通分量数量会变化。
考虑原因：
1. 若两个条件均不满足：则说明这个点不管正着还是反着，都不会有强连通分量产生，则不会变化。
2. 若两个条件均满足：则这两条路径拼起来就是一个强连通分量，缩点之后和 $u \rightarrow v$ 这条边的方向没有关系了，所以也不会变化。
3. 若仅有一个条件满足，则说明，如果没有 $u \rightarrow v$ 这条边，则原图中 $u$ 和 $v$ 一定不在同一个强连通分量中。而如果有了 $u \rightarrow v$ 或者 $v \rightarrow u$ 这条边，则分别结合条件 $1$ 和条件 $2$，就能让 $u$ 和 $v$ 在同一个强连通分量中，则说明翻转边一定会让强连通分量的数量改变。
然后考虑如何统计。
首先第一个条件直接 $O(NM)$ 爆搜统计就行了。
第二个条件乍一看有点辣手，但是仔细想想就会发现，它本质上就只是求：$u \rightarrow v$ 的路径中，这条边是不是必经边。你就考虑从 $x$ 开始 DFS，记录 $x$ 经过的点，被遍历到的时候 $x$ 的出边的标号。然后考虑将 $x$ 的出边顺序反过来再 DFS 一遍。如果两次遍历到的时候记录下来的标号不同，则说明 $u \rightarrow v$ 并不是必经边。反之则一定是必经边。
然后就枚举每条边瞎判判就行了。
${\rm Code}$：
```cpp
const int MAXN = 1010;
const int MAXM = 200010;
struct Edge {
int u, v;
Edge() {}
Edge(int u, int v):u(u), v(v) {}
}E[MAXM];
vector<int>to[MAXN];
int Mark[MAXN];
bitset<MAXN>vis;
bool G1[MAXN][MAXN];
bool G2[MAXN][MAXN];
inline void dfs1(int x, int st) {
G1[st][x] = 1, vis.set(x);
for(auto u : to[x]) if(!vis[u]) dfs1(u, st);
}
inline void dfs2(int x, int col, int k, int st) {
if(k) G2[st][x] = Mark[x] != col;
else Mark[x] = col; vis.set(x);
for(auto u : to[x]) if(!vis[u]) dfs2(u, col, k, st);
}
int main() {
int n = ri, m = ri;
for(int i = 1; i <= m; i++) {
int u = ri, v = ri;
to[u].push_back(v);
E[i] = Edge(u, v);
}
for(int i = 1; i <= n; i++) vis.reset(), dfs1(i, i);
for(int i = 1; i <= n; i++) {
vis.reset(), vis.set(i);
memset(Mark, 0, sizeof(Mark));
int d = to[i].size();
for(int j = 0; j < d; j++) if(!vis[to[i][j]]) dfs2(to[i][j], j + 1, 0, i);
vis.reset(), vis.set(i);
for(int j = d - 1; ~j; --j) if(!vis[to[i][j]]) dfs2(to[i][j], j + 1, 1, i);
}
for(int i = 1; i <= m; i++)
puts(G1[E[i].v][E[i].u] ^ G2[E[i].u][E[i].v] ? "diff" : "same");
return 0;
}
```