输入数据第一行是图顶点的数量，一个正整数N。 接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。
输出一行一个整数，表示该图的连通数。
对于100%的数据，N不超过2000。
用warshall算法求传递闭包即可
通过本题了解了bitset的使用orz
#include <bits/stdc++.h> using namespace std; bitset <2005> g[2005]; int n,ans; char s[2005]; int main(){ ans = 0; 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‘) g[i][j] = 1; if (i == j) g[i][j] = 1; } } for (int i = 1;i <= n;++i){ for (int j = 1;j <= n;++j){ if (g[j][i]) g[j] |= g[i]; } } for (int i = 1;i <= n;++i){ ans += g[i].count(); } printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/mizersy/p/9744972.html