输入数据第一行是图顶点的数量，一个正整数N。 接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。
输出一行一个整数，表示该图的连通数。
对于100%的数据，N不超过2000。
floyd+bitset传递闭包
#include <cstdio> #include <bitset> using namespace std; const int maxn = 2000 + 10; int n; bitset<maxn> dis[maxn]; char s[maxn]; int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%s", s + 1); for(int j = 1; j <= n; j++) if(s[j] == ‘1‘ || i == j) dis[i][j] = true; } for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) if(dis[i][k]) dis[i] |= dis[k]; int ans = 0; for(int i = 1; i <= n; i++) ans += dis[i].count(); printf("%d\n", ans); return 0; }
原文：https://www.cnblogs.com/ruoruoruo/p/7805252.html