邮件网站排名抖音推广方式有哪些

双连通分量

无向图中的双连通分量有两种：点双连通分量和边的连联通分量，如果去掉任意一个点之后，这个图还是连通的，就说这个图是点双连通的。如果去掉任意一条边之后这个图还是连通的，就说明这个图是边双连通的。

割桥将每一个边-双连通分量分开，low[i]的意义就是low[i]所连的块能返回的最早的祖先，也就是说，low[i]相同的点即为一个边连通分量。

Tips

• 点的下标是从0~n-1
• 使用该算法需要保证无重边
• 跑完模版之后，所有low[i]值相同的点的集合分别为一个边-双连通分量

//点-双连通分量
const int maxn=5000+10;//点数
struct Edge{int u,v;Edge(int _u,int _v){u = _u, v = _v;}
};
int pre[maxn]; //第一次访问的dfs_clock时间戳
int low[maxn];
int iscut[maxn]; //割点判断
int bccno[maxn]; // bccno[i]表示i所在最早访问的点-双联通分量的下标 即bcc[bccno[i]]这个连通分量集合中含有i这个点 对于割顶来讲没有意义，因为他属于多个点-双联通分量
vector<int> belong[maxn];//belong[i]表示i所在的双连通分量的下标的集合
int dfs_clock;
int bcc_cnt; // 双连通分量个数
vector<int>G[maxn]; // 顶点，下标0~n-1
vector<int>bcc[maxn]; //点双连通分量存储结果 下标1~bcnt
stack<Edge>S;
int dfs(int u,int fa){int lowu = pre[u] = ++dfs_clock;int child = 0;for (int i=0; i<G[u].size(); i++) {int v = G[u][i];Edge e = Edge(u, v);if (!pre[v]) {S.push(e);child++;int lowv = dfs(v, u);lowu = min(lowu, lowv);if (lowv >= pre[u]) {iscut[u] = true;bcc_cnt++;bcc[bcc_cnt].clear();while (true) {Edge x = S.top();S.pop();if (bccno[x.u]!=bcc_cnt) {bcc[bcc_cnt].push_back(x.u);bccno[x.u] = bcc_cnt;belong[x.u].push_back(bcc_cnt);}if (bccno[x.v] != bcc_cnt) {bcc[bcc_cnt].push_back(x.v);bccno[x.v] = bcc_cnt;belong[x.v].push_back(bcc_cnt);}if (x.u == u && x.v ==v) {break;}}}}else if(pre[v] < pre[u] && v != fa){S.push(e);lowu = min(lowu, pre[v]);}}if (fa < 0 && child == 1) {iscut[u] = 0;}return  low[u]=lowu;
}
int find_bcc(int n){//n个顶点//栈无需清空，每次跑完必然为空//bcc[]无需清空，组建连通分量时已清空memset(pre, 0, sizeof(pre));memset(iscut, 0, sizeof(iscut));memset(bccno, 0, sizeof(bccno));memset(low, 0, sizeof(low));dfs_clock = bcc_cnt = 0;int cnt = 0;for (int i=1; i<=n; i++) {if (!pre[i]) {dfs(i, -1);cnt++;}}return cnt;
}void work(int n,int m){// n个点 m条边// input and initializefor (int i=1; i<=n; i++) {G[i].clear();belong[i].clear();}for (int i=0; i<m; i++) {int u,v;scanf("%d%d",&u,&v);//index range: 1~nG[u].push_back(v);G[v].push_back(u);}// find biconnected componentint cnt = find_bcc(n);// outputprintf("共计%d个连通块\n",cnt);printf("共计%d个点-双连通分量\n",bcc_cnt);for (int i=1; i<=bcc_cnt; i++) {printf("第%d个点-双连通分量所含的点有: ",i);for (int j = 0; j<bcc[i].size(); j++) {printf("%d ",bcc[i][j]);}printf("\n");}
}
int main(){int n,m; //n个点 m条边while (scanf("%d%d",&n,&m)!=EOF) {work(n, m);}
}
/*
POJ 3352 Road Construction
给出一个没有重边的无向图，求至少加入几条边使整个图成为一个边双连通分量 
把图中所有的边双连通分量缩成一个点，原图就缩成了一棵树，
要加的边数就是(所有度为1的点的个数 + 1)/2
*/
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;#define MEM(a) memset(a, 0, sizeof(a))
#define pb push_back
const int maxv = 1010;int pre[maxv], low[maxv], deg[maxv], stakk[maxv];
int dfs_clock, top;
vector<int> G[maxv];void dfs(int u, int fa) {low[u] = pre[u] = ++dfs_clock;stakk[top++] = u;for (int i = 0; i < (int)G[u].size(); i++) {int v = G[u][i];if (!pre[v]) {dfs(v, u);low[u] = min(low[u], low[v]);} else if (pre[v] < pre[u] && v != fa) {low[u] = min(low[u], pre[v]);}}if (pre[u] == low[u]) {while (top > 0 && stakk[top] != u) {low[stakk[--top]] = low[u];}}
}void find_bcc(int n) {MEM(pre); MEM(low);MEM(deg);dfs_clock = top = 0;for (int i = 1; i <= n; i++)if (!pre[i]) dfs(i, -1);
}
int main() {int n, m, u, v;while (scanf("%d%d", &n, &m) != EOF) {for (int i = 1; i <= n; i++) G[i].clear();for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);G[u].pb(v); G[v].pb(u);}find_bcc(n);int ans = 0;for (int i = 1; i <= n; i++) {for (int j = 0; j < (int)G[i].size(); j++) {if (low[i] != low[G[i][j]]) {deg[low[i]]++;deg[low[G[i][j]]]++;}}}for (int i = 1; i <= n; i++)if (deg[i]/2 == 1) ans++;printf("%d\n", (ans+1)/2);}        return 0;
}
/*
LA 3523 Knights of the Round Table
亚瑟王要给一些骑士开会，但是这些骑士中有一些相互憎恨，
所以他们不能在圆桌中相邻，为了投票不出现支持的人数和反对的人数相等的情况，
每个圆桌中的骑士的个数必须为奇数个，
问有多少个骑士一定不能参加任何一个会议。
因为可能要开好几桌会议，所以要求出图中所有的连通分量，
又因为要求骑士的个数为奇数个，所以求每个联通分量中不在奇圈上的点的个数的和
*/
#include <cstdio>
#include <stack>
#include <cstring>
#include <vector>
using namespace std;#define MEM(a) memset(a, 0, sizeof(a))
const int maxv = 1100;
const int maxe = maxv*maxv;vector<int>G[maxv], bcc[maxv];
int dfs_clock, bcc_cnt, pre[maxv], low[maxv], bccno[maxv];
int color[maxv], odd[maxv], mapp[maxv][maxv];
struct Edge{int u, v;Edge(){}Edge(int a, int b) {u = a;v = b;}
};
stack<Edge> S;bool bipartite (int u, int b) {for (int i = 0; i < (int)G[u].size(); i++) {int v = G[u][i];if (bccno[v] != b) continue;if (color[v] == color[u]) return false;if (!color[v]) {color[v] = 3 - color[u];if (!bipartite(v, b)) return false;}}return true;
}void tarjan(int u, int fa) {pre[u] = low[u] = ++dfs_clock;for (int i = 0; i < (int)G[u].size(); i++) {int v = G[u][i];if (!pre[v]) {S.push(Edge(u, v));tarjan(v, u);low[u] = min(pre[v], low[u]);if (low[v] >= pre[u]) {bcc_cnt++;bcc[bcc_cnt].clear();for(;;) {Edge x = S.top(); S.pop();if (bccno[x.u] != bcc_cnt) {bcc[bcc_cnt].push_back(x.u);bccno[x.u] = bcc_cnt;}if (bccno[x.v] != bcc_cnt) {bcc[bcc_cnt].push_back(x.v);bccno[x.v] = bcc_cnt;}if (x.u == u && x.v == v) break;}}}else if (pre[v] < pre[u] && v != fa) {S.push(Edge(u, v));low[u] = min(low[u], pre[v]);}}
}void find_bcc(int n) {dfs_clock = bcc_cnt = 0;MEM(pre); MEM(low);for (int i = 1; i <= n; i++) if (!pre[i]) tarjan(i, -1);
}
int main() {int n, m, u, v;while (scanf("%d%d", &n, &m) != EOF &&m && n) {MEM(mapp);for (int i = 1; i <= n; i++) G[i].clear();for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);mapp[u][v] = mapp[u][v] = 1;}for (int u = 1; u <= n; u++) {for (int v = u+1; v <= n; v++) {if (!mapp[u][v]) {G[u].push_back(v);G[v].push_back(u);}}}find_bcc(n);MEM(odd);for (int i = 1; i <= bcc_cnt; i++) { //对于图中的每个点双连通分量MEM(color);for (int j = 0; j < (int)bcc[i].size(); j++) bccno[bcc[i][j]] = i;//给双连通分量里的每个点标号int u = bcc[i][0]; // 找到代表的点 (是割点？)color[u] = 1;if (!bipartite(u, i))   //判断如果这个双连通分量不是二分图，那么这个连通分量里的点都合格for (int j = 0; j < (int)bcc[i].size(); j++) odd[bcc[i][j]] = 1;}int ans = n;for (int i = 1; i <= n; i++) if (odd[i]) ans--;printf("%d\n", ans);}return 0;
}