制作团体网站,3000ok新开传奇网站公益服,建设工程教育网站,西安发布最新通知公告题目描述 在无向图中#xff0c;如果从顶点vi到顶点vj有路径#xff0c;则称vi和vj连通。如果图中任意两个顶点之间都连通#xff0c;则称该图为连通图#xff0c; 否则#xff0c;称该图为非连通图#xff0c;则其中的极大连通子图称为连通分量#xff0c;这里所谓的极… 题目描述 在无向图中如果从顶点vi到顶点vj有路径则称vi和vj连通。如果图中任意两个顶点之间都连通则称该图为连通图 否则称该图为非连通图则其中的极大连通子图称为连通分量这里所谓的极大是指子图中包含的顶点个数极大。 例如一个无向图有5个顶点1-3-5是连通的2是连通的4是连通的则这个无向图有3个连通分量。 输入 第一行是一个整数T表示有T组测试样例(0 T 50)。每个测试样例开始一行包括两个整数NM(0 N 20,0 M 200) 分别代表N个顶点和M条边。下面的M行每行有两个整数uv顶点u和顶点v相连。 输出 每行一个整数连通分量个数。示例输入 2
3 1
1 2
3 2
3 2
1 2 示例输出 2
1 提示 #include iostream #includecstdio #includecstring #includecstdlib using namespace std; typedef struct arcnode { int adj; }arcnode,adjmatrix[200][200]; typedef struct { adjmatrix a; int vn; int an; }MG; int create(MG g,int n,int m)//生成邻接矩阵 { int i,j; int v1,v2; g.vnn; g.anm; for(i1;ig.vn;i) for(j1;jg.vn;j) g.a[i][j].adj0; for(i1;ig.an;i) { scanf(%d%d,v1,v2); g.a[v1][v2].adj1; g.a[v2][v1]g.a[v1][v2]; } return 1; } int v[110];//标记图的顶点是否访问过 void dfs(MG g,int i)//深度优先搜索 { int j;//j在函数内部不然不能回溯 v[i]1; for(j1;jg.vn;j) if(g.a[i][j].adj1!v[j]) { dfs(g,j); } } int i,count;//记录连通分量个数 void dfs1(MG g)//统计连通分量的个数 { //int i;//若不在函数内部不会回溯 for(i1;ig.vn;i) if(!v[i]) { count; dfs(g,i); } } int main() { int t; MG g; scanf(%d,t); while(t--) { count0; memset(v,0,sizeof(v));//标记数组初始化 int n,m; scanf(%d%d,n,m); create(g,n,m); dfs1(g); printf(%d\n,count); } return 0; } #include cstdio
#define MAX 2000
using namespace std;int pre[MAX1];void Initialize(int n) { // 初始化各结点的 pre 为自身for(int i0; in; i) { // 相当于初始时每个结点为各自独立的集合pre[i] i;}
}int Find(int a) { // 查找 a 所在集合的根结点 rootint root a; // root 初始化为其本身while(pre[root] ! root) { // 当 root 的上级结点不是其本身root pre[root]; // 令 root 为它的上级结点继续查找}while(pre[a] ! root) { // 再次遍历路径压缩int temp pre[a];pre[a] root; // 沿途结点直接指向到 roota temp;}return root;
}void Join(int a, int b) { // 将 a, b 结点所在的集合合并int root_a Find(a); // 查找 a 所在集合的根结点int root_b Find(b); // 查找 b 所在集合的根结点if(root_a ! root_b) { // 如果 a, b 不在同一集合则合并if(root_a root_b) // 根结点下标大的集合并入下标小的集合pre[root_a] root_b;else pre[root_b] root_a;}
}int Count(int n) { // 统计不相交集合的个数int cnt 0; // 计数变量for(int i1; in; i) {int root Find(i); // 找到一个集合if(root) { // 如果是第一次找到此集合cnt; // 计数pre[root] 0; // 此根节点置0防止重复}}return cnt;
}int main(int argc, char const *argv[]) {int t, n, m, u, v;scanf(%d, t);while(t--) {scanf(%d %d, n, m);Initialize(n);while(m--) {scanf(%d %d, u, v);Join(u, v);}printf(%d\n, Count(n));}return 0;
}
