盐城北京网站建设,怎么用电脑做网站主机,微信小程序商城开源源码,网络推广运营公司双连通分量 无向图中的双连通分量有两种#xff1a;点双连通分量和边的连联通分量#xff0c;如果去掉任意一个点之后#xff0c;这个图还是连通的#xff0c;就说这个图是点双连通的。如果去掉任意一条边之后这个图还是连通的#xff0c;就说明这个图是边双连通的。 割桥… 双连通分量 无向图中的双连通分量有两种点双连通分量和边的连联通分量如果去掉任意一个点之后这个图还是连通的就说这个图是点双连通的。如果去掉任意一条边之后这个图还是连通的就说明这个图是边双连通的。 割桥将每一个边-双连通分量分开low[i]的意义就是low[i]所连的块能返回的最早的祖先也就是说low[i]相同的点即为一个边连通分量。 Tips 点的下标是从0~n-1 使用该算法需要保证无重边 跑完模版之后所有low[i]值相同的点的集合分别为一个边-双连通分量 //点-双连通分量
const int maxn500010;//点数
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这个点 对于割顶来讲没有意义因为他属于多个点-双联通分量
vectorint belong[maxn];//belong[i]表示i所在的双连通分量的下标的集合
int dfs_clock;
int bcc_cnt; // 双连通分量个数
vectorintG[maxn]; // 顶点下标0~n-1
vectorintbcc[maxn]; //点双连通分量存储结果 下标1~bcnt
stackEdgeS;
int dfs(int u,int fa){int lowu pre[u] dfs_clock;int child 0;for (int i0; iG[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 i1; in; i) {if (!pre[i]) {dfs(i, -1);cnt;}}return cnt;
}void work(int n,int m){// n个点 m条边// input and initializefor (int i1; in; i) {G[i].clear();belong[i].clear();}for (int i0; im; 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 i1; ibcc_cnt; i) {printf(第%d个点-双连通分量所含的点有: ,i);for (int j 0; jbcc[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;
vectorint 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, (ans1)/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;vectorintG[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;}
};
stackEdge 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 u1; 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;
}
