Description
Input
输入数据第一行是图顶点的数量，一个正整数N。 接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。
Output
输出一行一个整数，表示该图的连通数。
Sample Input
3
010
001
100
010
001
100
Sample Output
9
HINT
对于100%的数据，N不超过2000。
题目传送门
DFS！DFS！DFS！
重要的事情说三遍
妈的这道题有毒！
神TM我真的是服了我这个SB
我打了半天的他人tarjan错了不说，随便叫了1个DFS玩儿一下都过了。。
苍天不公啊！
代码如下：
#include<cmath>#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>using namespace std;struct node{ ???int x,y,next;}a[4100000];int len,last[4100000];void ins(int x,int y){ ???len++; ???a[len].x=x;a[len].y=y; ???a[len].next=last[x];last[x]=len;}int n;bool v[21000];char st[21000];void dfs(int x){ ???v[x]=1; ???for(int k=last[x];k;k=a[k].next) ???????if(v[a[k].y]==false)dfs(a[k].y);}int main(){ ???scanf("%d",&n); ???len=0;memset(last,0,sizeof(last)); ???for(int i=1;i<=n;i++) ???{ ???????scanf("%s",st+1); ???????for(int j=1;j<=n;j++) ???????????if(st[j]==‘1‘) ???????????????ins(i,j); ???} ???int ans=0; ???for(int i=1;i<=n;i++) ???{ ???????memset(v,false,sizeof(v)); ???????dfs(i); ???????for(int j=1;j<=n;j++)ans+=v[j]; ???} ???printf("%d\n",ans); ???return 0;}BZOJ2208: [Jsoi2010]连通数
原文地址：https://www.cnblogs.com/MT-LI/p/8424385.html