考虑反转一条边 \(u\rightarrow v\) 后强连通分量数量变化的条件。
- 如果 \(v\) 能到 \(u\) 且 \(u\) 到 \(v\) 必须经过这条边，那么翻转后强连通分量数量会减少。
- 如果 \(v\) 不能到 \(u\) 且 \(u\) 到 \(v\) 可以不经过这条边，那么翻转后强连通分量会变多。
如果不符合以上两种情况，翻转后强连通分量数量不变。
现在对于每一条边 \(u\rightarrow v\)，只需要求出 \(v\) 是否能到 \(u\)，以及 \(u\rightarrow v\) 的路径中该边是否为必经边。
第一个简单，直接 \(\mathcal{O}(n\times m)\) 暴力求。第二个是个经典问题可是我不会。
具体的，对于一个点 \(u\)，正序遍历 \(u\) 的每一条出边，只访问没被标记的点，给他们打上这个边的标记，这个被称之为第一次遍历。然后清空访问数组，反着遍历 \(u\) 的每一条出边，如果点 \(v\) 在第一次遍中被打的边标记和当前访问到 \(v\) 的边不是同一条边，那就有至少两种路径从 \(u\) 到 \(v\)，否则只有一种。这样就可以在 \(\mathcal{O}(n\times m)\) 的时间内求出每一条边是否为必经边了。
查寻直接判断。
总时间复杂度 \(\mathcal{O}(n\times m)\)。
代码
#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>inline void read(T&x){x=0;char c=getchar();bool f=0;while(!isdigit(c)) c=='-'?f=1:0,c=getchar();while(isdigit(c)) x=x*10+c-'0',c=getchar();f?x=-x:0;}template<typename T>inline void write(T x){if(x==0){putchar('0');return ;}x<0?x=-x,putchar('-'):0;short st[50],top=0;while(x) st[++top]=x%10,x/=10;while(top) putchar(st[top--]+'0');}inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}inline void write(char c){putchar(c);}inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
const int maxn=1010,maxm=200010;
int n,m,c[maxn],bh[maxn][maxn];
vector<int>e[maxn];
struct EDGE{int u,v;
}b[maxm];
bool flag[maxn],to[maxn][maxn],nd[maxm];
void dfs1(int u,int st){if(to[st][u]) return ;to[st][u]=1;for(auto v :e[u]) dfs1(v,st);
}
void dfs2(int u,int col){if(flag[u]) return ;flag[u]=1,c[u]=col;for(auto v:e[u]) dfs2(v,col);
}
void dfs3(int u,int col,int st){if(flag[u]) return ;flag[u]=1;if(bh[st][u]&&c[u]!=col) nd[bh[st][u]]=1;for(auto v:e[u]) dfs3(v,col,st);
}
signed main(){read(n,m);for(int i=1;i<=m;i++){int u,v;read(u,v);bh[u][v]=i;e[u].push_back(v);b[i]={u,v};}for(int i=1;i<=n;i++) dfs1(i,i);for(int i=1;i<=n;i++){memset(c,0,sizeof(c)),memset(flag,0,sizeof(flag));flag[i]=1;int col=0;for(auto v:e[i]) col++,dfs2(v,col);memset(flag,0,sizeof(flag));flag[i]=1;for(int j=e[i].size()-1;j>=0;j--){dfs3(e[i][j],col,i);col--;}}for(int i=1;i<=m;i++) if(nd[i]^to[b[i].v][b[i].u]) write("diff\n");else write("same\n");return 0;
}