加快门户网站建设,dede网站搬家教程,手机网站建设公司电话咨询,wordpress调用文章第一张图片题目
水题系列。给出一个图#xff0c;求他的连通分量。 科普#xff1a;连通分量就是一个图中可以连接最多点的子图#xff08;可以是它本身#xff09;的点数量。
输入
5(点的数量) 1 2(表示1和2连通) 3 4 2 3 0 0(表示停止输入)
输出
4 解题思路
Er…这道题没…题目
水题系列。给出一个图求他的连通分量。 科普连通分量就是一个图中可以连接最多点的子图可以是它本身的点数量。
输入
5(点的数量) 1 2(表示1和2连通) 3 4 2 3 0 0(表示停止输入)
输出
4 解题思路
Er…这道题没什么难度反正两种做法dfs,bfs都贴出来。 dfs代码
#includecstdio
#includeiostream
using namespace std;
int walk[101],a[101][101],x,y,maxs,n;
int s;
int dfs(int x)
{s;//表示搜到的点数加walk[x]true;//封上for (int i1;in;i){if (a[i][x] !walk[i]){dfs(i);//搜索}}
}
int main()
{scanf(%d,n);while (true){scanf(%d%d,x,y);if (x0 y0) break;a[x][y]true;a[y][x]true;}for (int i1;in;i)if (!walk[i]) {s0;dfs(i);maxsmax(maxs,s);}//搜出一个子图printf(%d,maxs);
} bfs代码(不解释)
#includecstdio
#includeiostream
using namespace std;
int walk[101],a[101][101],state[101],x,y,maxs,n;
int head,tail;
int bfs(int x)
{state[1]x;walk[x]true;head0;tail1;do{head;xstate[head];for (int i1;in;i){if (!walk[i] a[x][i]){tail;state[tail]i;walk[i]true;}}}while (headtail);maxsmax(maxs,tail);
}
int main()
{scanf(%d,n);while (true){scanf(%d%d,x,y);if (x0 y0) break;a[x][y]true;a[y][x]true;}for (int i1;in;i)if (!walk[i]) bfs(i);printf(%d,maxs);
}
