整理的算法模板合集： ACM模板
题目要求删除一条边整个图的连通性是不受影响的，也就是说如果我们要删除边 ( x , y ) (x,y) (x,y)，删除以后整个图的连通性不受影响的条件很明显就是x到y之间至少还有一条边可以到达。所以我们要统计每对点之间的路径条数，对于每一条边 ( x , y ) (x, y) (x,y)来说，如果xy之间至少有两条路径，那么这一条边就可以删除，ans++ 。由于这是一个有向无环图，所以保证正确性。 我们直接拓扑排序，类似可达性统计的那一道题，我们可以用bitset存，先处理出每对点路径条数大于等于1的，用A存，再处理路径条数大于等于2的情况，用B存，我们只需要按照拓扑序倒序递推，对于每一对点x和y，B加上A[x] & A[y]表示x能到达z，y也能到达，z那么说明x和y之间至少还有一条边都能到达z，也就是x与y之间的路径条数至少大于等于2。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<bitset> #include<queue> using namespace std; typedef long long ll; typedef unsigned long long ull;//卡精度 typedef pair<int,int> PII; const int N = 3e4+7, M = 3e5 + 7; const ll mod = 1e9+7; const ll INF = 1e15+7; const double EPS = 1e-10;//可近似为趋近为 0 可以根据定义求导时使用 const int base = 131;//base = 13331 // hash bitset<N>A[N], B[N]; int n, m; int head[N], ver[M], edge[M], nex[M], tot; int in[N]; int ans[M], top; void add(int x, int y) { ver[tot] = y; nex[tot] = head[x]; head[x] = tot ++ ; in[y] ++ ; } void toposort() { queue<int>q; for(int i = 1; i <= n; ++ i) if(in[i] == 0) q.push(i); while(q.size()) { int x = q.front(); q.pop(); ans[++ top] = x; for(int i = head[x]; ~i; i = nex[i]){ int y = ver[i]; in[y] -- ; if(in[y] == 0) q.push(y); } } return ; } void solve() { for(int k = top ;k >= 1; -- k){ int x = ans[k]; for(int i = head[x]; ~i; i = nex[i]){ int y = ver[i]; //我们倒序从叶子节点开始 B[x] |= (A[y] & A[x]); //y能到，x也能到，并且x可以到y说明x到y至少有2条路径 A[x] |= A[y]; } } } int main() { memset(head, -1, sizeof head); scanf("%d%d", &n, &m); for(int i = 1; i <= m; ++ i){ int x, y; scanf("%d%d", &x, &y); add(x, y); } for(int i = 1; i <= n; ++ i) A[i][i] = 1; toposort(); solve(); int ans = 0; for(int x = 1; x <= n; ++ x){ for(int i = head[x]; ~i; i = nex[i]){ int y = ver[i]; if(B[x][y] == 1)ans ++ ;//这里应该判断x到y==1 } } //for(int i = 1; i <= n; ++ i)//可以直接交可达性统计那一道题 // printf("%d\n", A[i].count()); printf("%d\n", ans); return 0; }