【BZOJ2208】【JSOI2010】连通数

。。。。。。

// <2208.cpp> - 08/17/16 15:15:27
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
bool gb(){
    char ch=getchar();
    while(ch!='0'&&ch!='1')ch=getchar();
    return ch=='1';
}
const int MAXN=2010;
const int MAXM=MAXN*MAXN;
const int INF=1e9;
int bt,b[MAXN],next[MAXM],to[MAXM];
inline void add(int x,int y){next[++bt]=b[x];b[x]=bt;to[bt]=y;}
int vis[MAXN];
queue <int> q;
int main(){
    int n=gi(),ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)if(gb())add(i,j);
    for(int i=1;i<=n;i++){
        vis[i]=i;q.push(i);
        while(!q.empty()){
            int x=q.front();q.pop();ans++;
            for(int j=b[x];j;j=next[j])
                if(vis[to[j]]!=i){
                    vis[to[j]]=i;
                    q.push(to[j]);
                }
        }
    }
    printf("%d",ans);
    return 0;
}

// <2208.cpp> - 08/17/16 15:15:27

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

bool gb(){

char ch=getchar();

while(ch!='0'&&ch!='1')ch=getchar();

return ch=='1';

}

const int MAXN=2010;

const int MAXM=MAXN*MAXN;

const int INF=1e9;

int bt,b[MAXN],next[MAXM],to[MAXM];

inline void add(int x,int y){next[++bt]=b[x];b[x]=bt;to[bt]=y;}

int vis[MAXN];

queue <int> q;

int main(){

int n=gi(),ans=0;

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)if(gb())add(i,j);

for(int i=1;i<=n;i++){

vis[i]=i;q.push(i);

while(!q.empty()){

int x=q.front();q.pop();ans++;

for(int j=b[x];j;j=next[j])

if(vis[to[j]]!=i){

vis[to[j]]=i;

q.push(to[j]);

}

printf("%d",ans);

return 0;

}