【搜索】[AtCoder Regular Contest 092 F]Two Faced Edges

题意：

给出一个有向图，对每条边都做一次询问：
反转这条边后，对原图的强连通分量是否有影响？
点的个数$N\leq 1000$，边的个数$M\leq 200000$

分析：

首先对于原图的任意一条边$(u,v)$如果反转之后，对强连通分量无影响，则：
1、u是否能通过其他边到达v
2、v是否能到达u
这两个问题的答案必须相同。
其实是比较简单的性质，但很难往这边想，仔细想想就明白了。

对于第二个问题，我们只需要从每个点出发，对全图跑一次DFS记录哪些点能到即可，复杂度$O(NM)$。
对于第一个问题，则稍微复杂一点：
对于一个点$x$，我们将其所有出边的点设为$y_1,y_2……y_k$
我们进行如下操作：
从$y_1到y_k$每个点依次出发，设当前的点为$y_i$
若当前的点未被标记，则标记为$i$，若已有标记，则退出。

然后，再从$y_k$到$y_1$每个点依次出发，仍然设当前点为$y_i$
和之前一样，只是要和上一次独立开来，用另一个数组存储标记。
若当前的点未被标记，则标记为$i$，若已有标记，则退出。

这样一来，我们可以知道从$x$出发，到达任意一个点时，所经过的最小出边序号和最大出边序号。很显然，若两个值相同，则说明只能通过一条出边到达该点。那么这样一来，我们可以对$y_1,y_2……y_k$依次判断，若到达改点的最小出边序号和最大出边序号，均为该出边本身，则说明不能从$x$出发，经过其他边到达该点。
这样一来，每次最多也只会访问$M$条边进行标记，最终的复杂度也为$O(NM)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 1010
#define MAXM 200010
using namespace std;
int n,m,u,v;
int id[MAXN][MAXN],ans1[MAXN][MAXN],ans2[MAXN][MAXN],q[MAXN][2];
int ans[MAXM];
vector<int> a[MAXN];
void dfs(int x,int fa){ans1[fa][x]=1;for(int i=0;i<a[x].size();i++)if(ans1[fa][a[x][i]]==0)dfs(a[x][i],fa);
}
void dfs1(int x,int tag,int flag){q[x][flag]=tag;for(int i=0;i<a[x].size();i++)if(!q[a[x][i]][flag])dfs1(a[x][i],tag,flag);
}
int main(){SF("%d%d",&n,&m);for(int i=0;i<m;i++){SF("%d%d",&u,&v);u--;v--;id[u][v]=i+1;a[u].push_back(v);}for(int i=0;i<n;i++)dfs(i,i);for(int i=0;i<n;i++){memset(q,0,sizeof q);q[i][0]=q[i][1]=-1;for(int j=0;j<a[i].size();j++)if(!q[a[i][j]][0])dfs1(a[i][j],j+1,0);for(int j=a[i].size()-1;j>=0;j--)if(!q[a[i][j]][1])dfs1(a[i][j],j+1,1);for(int j=0;j<a[i].size();j++)if(q[a[i][j]][0]!=j+1||q[a[i][j]][1]!=j+1)ans2[i][a[i][j]]=1;}for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(ans1[j][i]==ans2[i][j]&&id[i][j])ans[id[i][j]]=1;for(int i=1;i<=m;i++){if(ans[i]==1)PF("same\n");elsePF("diff\n");}
}