畅通工程2查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb某省调查城镇交通状况得到现有城镇道路统计表表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通但不一定有直接的道路相连只要互相间接通过道路可达即可。问最少还需要建设多少条道路输入输出格式输入描述:测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数分别是城镇数目N ( 1000 )和道路数目M随后的M行对应M条道路每行给出一对正整数分别是该条道路直接连通的两个城镇的编号。为简单起见城镇从1到N编号。 注意:两个城市之间可以有多条道路相通,也就是说 3 3 1 2 1 2 2 1 这种输入也是合法的 当N为0时输入结束该用例不被处理。输出描述:对每个测试用例在1行里输出最少还需要建设的道路数目。输入输出样例输入样例#:复制4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0输出样例#:复制1 0 2 998题目来源浙江大学机试题#includebits/stdc.h using namespace std; int s[10005]; int fa[1005]; int find(int x){ if(fa[x] x){ return x; } else{ fa[x] find(fa[x]); return fa[x]; } } void join(int x, int y){ int rootx find(x); int rooty find(y); if(rootx ! rooty){ fa[rootx] rooty; } } int main(){ int n, m; while(cinnm){ for(int i 1; i n; i ){ fa[i] i; } int x, y; for(int i 0; i m; i ){ cinxy; if(x y){//统一让小的在前 swap(x, y); } join(x, y); } int count 0; int root find(1); for(int i 1; i n; i ){ int rooti find(i); // couti:rootiendl; if(rooti ! root){//没联通 join(i, 1); count ; } } coutcountendl; }// }图的连通分支数查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb该题的目的是要你统计图的连通分支数。输入输出格式输入描述:每个输入文件包含若干行每行两个整数i,j表示节点i和j之间存在一条边。输出描述:输出每个图的联通分支数。输入输出样例输入样例#:复制1 4 4 3 5 5输出样例#:复制2题目来源上海交通大学机试题#includebits/stdc.h using namespace std; int fa[100005]; int s[100005]; int find(int x){ if(fa[x] x){ return fa[x]; } else{ fa[x] find(fa[x]); return fa[x]; } } void join(int x, int y){ int rootx find(x); int rooty find(y); if(rootx rooty){ return; } else{ fa[rootx] rooty;//y变成了老大 } } int main(){ int n, m; for(int i 1; i 10000; i ){ fa[i] i; s[i] 0; } int x, y, root; while(cinxy){ join(x, y); s[x] 1; s[y] 1; } int count 0; for(int i 1; i 10000; i ){ // couti find(i)endl; if(s[i] 1){//有点 if(find(i) i){ count ; } } } coutcountendl; }极大连通图个数查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb给指定矩阵由.和w组成求w能组成的极大连通图个数可以斜着(也就是八个方向)。输入输出格式输入描述:第一行输入两个数代表矩阵的行数h和列数w1wh100 接下来输入这个矩阵输出描述:如题输入输出样例输入样例#:复制5 10 ..w.....ww .ww..wwwww .w...w.... ..wwww.www ..wwww.www输出样例#:复制2题目来源四川大学2024年机试题#includebits/stdc.h using namespace std; const int N 105; const int INF 0x3f3f3f3f; char g[105][105]; int visit[105][105]; int dx[8] {-1, -1, -1, 0, 1, 1, 1, 0}; int dy[8] {-1, 0, 1, 1, 1, 0, -1, -1}; int h, w; void DFS(int x, int y){ g[x][y] .; for(int i 0; i 8; i ){ int sx x dx[i]; int sy y dy[i]; if(sx 0 || sx h || sy 0 || sy w){ continue; } if(g[sx][sy] .){ continue; } if(g[sx][sy] w){ DFS(sx, sy); } } } int main(){ int m, n; cinhw; for(int i 0; i h; i ){ for(int j 0; j w; j ){ cing[i][j]; } } int count 0; for(int i 0; i h; i ){ for(int j 0; j w; j ){ if(g[i][j] w){ DFS(i, j); count ; // for(int i 0; i h; i ){ // for(int j 0; j w; j ){ // coutg[i][j] ; // } // coutendl; // } // } } } coutcountendl; }//end
畅通工程cccccccc
畅通工程2查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb某省调查城镇交通状况得到现有城镇道路统计表表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通但不一定有直接的道路相连只要互相间接通过道路可达即可。问最少还需要建设多少条道路输入输出格式输入描述:测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数分别是城镇数目N ( 1000 )和道路数目M随后的M行对应M条道路每行给出一对正整数分别是该条道路直接连通的两个城镇的编号。为简单起见城镇从1到N编号。 注意:两个城市之间可以有多条道路相通,也就是说 3 3 1 2 1 2 2 1 这种输入也是合法的 当N为0时输入结束该用例不被处理。输出描述:对每个测试用例在1行里输出最少还需要建设的道路数目。输入输出样例输入样例#:复制4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0输出样例#:复制1 0 2 998题目来源浙江大学机试题#includebits/stdc.h using namespace std; int s[10005]; int fa[1005]; int find(int x){ if(fa[x] x){ return x; } else{ fa[x] find(fa[x]); return fa[x]; } } void join(int x, int y){ int rootx find(x); int rooty find(y); if(rootx ! rooty){ fa[rootx] rooty; } } int main(){ int n, m; while(cinnm){ for(int i 1; i n; i ){ fa[i] i; } int x, y; for(int i 0; i m; i ){ cinxy; if(x y){//统一让小的在前 swap(x, y); } join(x, y); } int count 0; int root find(1); for(int i 1; i n; i ){ int rooti find(i); // couti:rootiendl; if(rooti ! root){//没联通 join(i, 1); count ; } } coutcountendl; }// }图的连通分支数查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb该题的目的是要你统计图的连通分支数。输入输出格式输入描述:每个输入文件包含若干行每行两个整数i,j表示节点i和j之间存在一条边。输出描述:输出每个图的联通分支数。输入输出样例输入样例#:复制1 4 4 3 5 5输出样例#:复制2题目来源上海交通大学机试题#includebits/stdc.h using namespace std; int fa[100005]; int s[100005]; int find(int x){ if(fa[x] x){ return fa[x]; } else{ fa[x] find(fa[x]); return fa[x]; } } void join(int x, int y){ int rootx find(x); int rooty find(y); if(rootx rooty){ return; } else{ fa[rootx] rooty;//y变成了老大 } } int main(){ int n, m; for(int i 1; i 10000; i ){ fa[i] i; s[i] 0; } int x, y, root; while(cinxy){ join(x, y); s[x] 1; s[y] 1; } int count 0; for(int i 1; i 10000; i ){ // couti find(i)endl; if(s[i] 1){//有点 if(find(i) i){ count ; } } } coutcountendl; }极大连通图个数查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb给指定矩阵由.和w组成求w能组成的极大连通图个数可以斜着(也就是八个方向)。输入输出格式输入描述:第一行输入两个数代表矩阵的行数h和列数w1wh100 接下来输入这个矩阵输出描述:如题输入输出样例输入样例#:复制5 10 ..w.....ww .ww..wwwww .w...w.... ..wwww.www ..wwww.www输出样例#:复制2题目来源四川大学2024年机试题#includebits/stdc.h using namespace std; const int N 105; const int INF 0x3f3f3f3f; char g[105][105]; int visit[105][105]; int dx[8] {-1, -1, -1, 0, 1, 1, 1, 0}; int dy[8] {-1, 0, 1, 1, 1, 0, -1, -1}; int h, w; void DFS(int x, int y){ g[x][y] .; for(int i 0; i 8; i ){ int sx x dx[i]; int sy y dy[i]; if(sx 0 || sx h || sy 0 || sy w){ continue; } if(g[sx][sy] .){ continue; } if(g[sx][sy] w){ DFS(sx, sy); } } } int main(){ int m, n; cinhw; for(int i 0; i h; i ){ for(int j 0; j w; j ){ cing[i][j]; } } int count 0; for(int i 0; i h; i ){ for(int j 0; j w; j ){ if(g[i][j] w){ DFS(i, j); count ; // for(int i 0; i h; i ){ // for(int j 0; j w; j ){ // coutg[i][j] ; // } // coutendl; // } // } } } coutcountendl; }//end
