wordpress 用户站点,兰州网站建设哪家好,上海网站建设开发哪家专业,企业网站开发创意求连通分量
ssl 1759
题目大意
由n个点组成的无向图#xff0c;求连通在一起的点数最大是多少 原题
求一个图的连通分量 Input
n 顶点数(100)
边
Output
连通分量
Sample Input
8
6 3
1 2
2 5
5 4
4 1
8 7
0 0
Sample Output
4 方法一#xff08;dfs …求连通分量
ssl 1759
题目大意
由n个点组成的无向图求连通在一起的点数最大是多少 原题
求一个图的连通分量 Input
n 顶点数(100)
边
Output
连通分量
Sample Input
8
6 3
1 2
2 5
5 4
4 1
8 7
0 0
Sample Output
4 方法一dfs 邻接矩阵
用邻接矩阵的方法来存再用dfs要判断到过没
#includecstdio
#includeiostream
using namespace std;
int n,x,y,a[101][101],ans;
bool p[101];
int dfs(int now)
{int t1;//自身p[now]1;//记录for (int i1;in;i)if ((!p[i])(a[now][i]))//到过未连不连通tdfs(i);//累加return t;
}
int main()
{scanf(%d%d%d,n,x,y);while(xy){a[x][y]1;a[y][x]1;//正反都要scanf(%d%d,x,y);}for (int i1;in;i)if (!p[i])ansmax(ans,dfs(i));//求总值printf(%d,ans);
}方法二dfs 邻接表
用dfs,但是用链表的方法存搜索时就省了很多时间
#includecstdio
#includeiostream
using namespace std;
int s[101],n,x,y,ans,w;
bool p[101];
struct rec
{int ss,next;//ss为连接的数next和同一个点的另一条线
}a[10005];
int dfs(int now)
{int t1;//自身p[now]1;//已走过for (int is[now];i;ia[i].next)//以now为起点的所有边if (!p[a[i].ss]) tdfs(a[i].ss);//判断到过没没到过就去return t;
}
int main()
{scanf(%d%d%d,n,x,y);while (xy){a[w].ssy;//下一个数a[w].nexts[x];//下一条边s[x]w;//替换a[w].ssx;//反过来做一遍无向a[w].nexts[y];s[y]w;scanf(%d%d,x,y);}for (int i1;in;i)if (!p[i])ansmax(ans,dfs(i));//求最大值printf(%d,ans);
}方法三bfs 邻接矩阵
同样是用邻接矩阵但用bfs从每一个位置开始结果为队列的长度
**#includecstdio
#includeiostream
using namespace std;
int n,x,y,a[101][101],p[101],d[101],ans;
int bfs(int x)
{int head0,tail1;d[1]x;//入队p[x]1;//记录do{head;for (int i1;in;i)if ((!p[i])(a[d[head]][i]))//是否可到到过没{d[tail]i;//入队p[i]1;//记录}}while(headtail);return tail;//结果就是长度
}
int main()
{scanf(%d%d%d,n,x,y);while (xy){a[x][y]1;a[y][x]1;scanf(%d%d,x,y);}for (int i1;in;i)if (!p[i])//判断ansmax(ans,bfs(i));printf(%d,ans);return 0;
}**方法四(bfs 邻接表)
用bfs和邻接表二三内容基本就是方法二和方法三的合成体
#includecstdio
#includeiostream
int n,x,y,w,ans,p[101],s[101],d[101];
using namespace std;
struct rec
{int ss,next;//定义
}a[10005];
int bfs(int now)
{int head0,tail1;d[1]now;//预处理p[now]1;//记录do{head;for (int is[d[head]];i;ia[i].next)//同一个点连接的不同线if (!p[a[i].ss])//判断到过没{p[a[i].ss]1;//记录d[tail]a[i].ss;//入队}}while(headtail);return tail;
}
int main()
{scanf(%d%d%d,n,x,y);while (xy){a[w].ssy;//后面的数a[w].nexts[x];//同一个点的其他线s[x]w;//代替a[w].ssx;//相反a[w].nexts[y];s[y]w;scanf(%d%d,x,y);}for (int i1;in;i)if (!p[i])ansmax(ans,bfs(i));printf(%d,ans);return 0;
}方法五The lastbfs 邻接表——STL{\color{Red}STL}STL
个方法四基本相同但运用了一种鲜为人我知的技术——STLqueue,改了一些地方
#includecstdio
#includeiostream
#includequeue
int n,x,y,w,ans,p[101],s[101],d[101];
using namespace std;
struct rec
{int ss,next;
}a[10005];
int bfs(int now)
{int g,jg1;queueintd;d.push(now);//在尾端插入p[now]1;while(d.size()){gd.front();//队头d.pop();//队头出列for (int is[g];i;ia[i].next)//基本前面的if (!p[a[i].ss]){jg;//结果p[a[i].ss]1;d.push(a[i].ss);//入队}}return jg;
}
int main()
{scanf(%d%d%d,n,x,y);while (xy){a[w].ssy;a[w].nexts[x];s[x]w;a[w].ssx;a[w].nexts[y];s[y]w;scanf(%d%d,x,y);}for (int i1;in;i)if (!p[i])ansmax(ans,bfs(i));printf(%d,ans);//和方法四一样的主程序return 0;
}
