海淀区网站备案去哪,最新网站推广,视频门户网站建设项目标书,优化网站标题和描述的方法正题
题目链接:https://www.luogu.com.cn/problem/AT3945 题目大意 nnn个点mmm条边的一张图#xff0c;对于每条边求它翻转后强连通分量数量是否变化。 1≤n≤1000,1≤m≤21051\leq n\leq 1000,1\leq m\leq 2\times 10^51≤n≤1000,1≤m≤2105 解题思路
对于一条(x,y)(x,y)(…正题
题目链接:https://www.luogu.com.cn/problem/AT3945 题目大意
nnn个点mmm条边的一张图对于每条边求它翻转后强连通分量数量是否变化。
1≤n≤1000,1≤m≤2×1051\leq n\leq 1000,1\leq m\leq 2\times 10^51≤n≤1000,1≤m≤2×105 解题思路
对于一条(x,y)(x,y)(x,y)的边。
如果原来yyy能走到xxx那么考虑现在是否强连通分量是否减少就是说如果存在一条x−yx-yx−y的路径不经过这条边那么不变否则减少。如果原来yyy不能走到xxx那么考虑现在强连通分量是否增加那么如果存在一条x−yx-yx−y的路径不经过这条边那么就会产生一个新的强连通分量。
考虑每一个xxx能否走到yyy这个直接暴力O(nm)O(nm)O(nm)预处理就好了。
然后考虑对于每条边x,yx,yx,yxxx能否不经过这条边走到yyy从xxx开始dfsdfsdfs记录出去的第一条边然后如果到一个点有两种不同情况那么标记即可。
时间复杂度O(nm)O(nm)O(nm) code
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
const int N1e310,M2e510;
int n,m,f[N][N],g[N][N],X[M],Y[M];
vectorint a[N];
void step(int x,int *v){if(v[x])return;v[x]1;for(int i0;ia[x].size();i)step(a[x][i],v);
}
void calc(int x,int *v){if(v[x]1)return;v[x]1;for(int i0;ia[x].size();i)calc(a[x][i],v);return;
}
void dfs(int x,int *v,int pos){if(v[x]0)return;else if(v[x]0){if((-v[x])pos)return;else v[x]1;}else if(!v[x])v[x]-pos;for(int i0;ia[x].size();i)if(v[x]1)calc(a[x][i],v);else dfs(a[x][i],v,pos);return;
}
int main()
{scanf(%d%d,n,m);for(int i1;im;i){int x,y;scanf(%d%d,x,y);a[x].push_back(y);X[i]x;Y[i]y;}for(int i1;in;i)step(i,f[i]);for(int x1;xn;x){g[x][x]1;for(int i0;ia[x].size();i)dfs(a[x][i],g[x],i1);}for(int i1;im;i){if(f[Y[i]][X[i]]){if(g[X[i]][Y[i]]1)puts(same);else puts(diff);}else{if(g[X[i]][Y[i]]1)puts(diff);else puts(same);}}return 0;
}
