题解 P4306 【[JSOI2010]连通数】

SugarSBN · 2018-12-06 21:45:51 · 题解

这什么题？ 不是暴力O(n^2)就行了嘛？？？ 这是JSOI？还是luogu数据太弱？。。

#define For(a,b,c) for (int (a)=(b);(a)<(c);(a)++)
int n,ans;
char G[2001][2001];
bool vis[2001];
void dfs(int u){
    ans++;
    vis[u] = 1;
    For(i,0,n)  if (G[u][i] == '1' && !vis[i])  dfs(i);
}
int main(){
//  freopen("in.txt","r",stdin);
    scanf("%d",&n);
    For(i,0,n)  scanf("%s",G[i]);
    For(i,0,n){
        memset(vis,0,sizeof(vis));
        dfs(i);
    }
    printf("%d\n",ans);
    return 0;
}