[JSOI2010]连通数（dfs或tarjan或bitset）+bitset学习

题目描述

输入格式

输入数据第一行是图顶点的数量，一个正整数N。接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。

输出格式

输出一行一个整数，表示该图的连通数。

样例

样例输入

样例输出

数据范围与提示

对于100%的数据，N不超过2000。

solution：

这道题给出三种算法：

DFS：

这道题搜索可以过

用vecter建边，若有一条由i指向j的边，那么把j压到i的vector中（这种建边方法好像比前向星快）

建立bool数组vis，vis[i][j]=1表示已经访问过由i指向j的边

我们对于每一个点进行dfs，其中dfs(i,j)表示以i为起点开始搜索，当前搜到了j点，依次向下dfs并统计答案

由于这里的vis存的是边的信息，所以不用考虑环。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<vector>

 #define MAXN 2005

 using namespace std;

 int n,ans[MAXN],res=;

 char ch[MAXN][MAXN];

 vector<int>mapa[MAXN];

 bool vis[MAXN][MAXN];//vis[i][j]表示是否访问过由i向j的边

 void dfs(int st,int now){//st:起点,now:当前节点

     ans[st]++;

     vis[st][now]=;

     int m=mapa[now].size();

     for(int i=;i<m;i++){

         if(!vis[st][mapa[now][i]])

             dfs(st,mapa[now][i]);

     }

 }

 int main(){

     scanf("%d",&n);

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

         scanf("%s",ch[i]+);

         for(int j=;j<=n;j++){

             if(ch[i][j]=='')

                 mapa[i].push_back(j);

             //cout<<ch[i][j];

         }

         //cout<<endl;

     }

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

         dfs(i,i),res+=ans[i];

     printf("%d\n",res);

     return ;

 }

代码在这里！

TARJAN：

缩点再建图，这是最主流的方法，不再赘述：

#include<bits/stdc++.h>

using namespace std;

bitset<> t[];

int n,ans=,e[],in[];char s[];

int dfn[],low[],st[],num=,top=,cnt=;

bool ins[];

int tot=,first[],len[];

vector<int> edge[],scc[];

struct node{int v,next;}eg[];

inline void add(int x,int y)

{

    eg[++tot].v=y;

    eg[tot].next=first[x];

    first[x]=tot;

}

inline void tarjan(int x)

{

    dfn[x]=low[x]=++num;

    st[++top]=x;ins[x]=;

    for(register int i=;i<edge[x].size();i++)

    {

        int to=edge[x][i];

        if(!dfn[to])

        {

            tarjan(to);

            low[x]=min(low[x],low[to]);

        }

        else if(ins[to])

            low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        cnt++;int y;

        do{

            y=st[top--],ins[y]=;

            t[cnt][y]=,++len[cnt];

            e[y]=cnt,scc[cnt].push_back(y);

        }while(x!=y);

    }

}

int main()

{

    scanf("%d",&n);

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

    {

        scanf("%s",s+);

        for(register int j=;j<=n;j++)

            if(s[j]=='')edge[i].push_back(j);

    }

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

        if(!dfn[i])tarjan(i);

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

        for(register int j=;j<edge[i].size();j++)

        {

            int to=edge[i][j];

            if(e[i]==e[to])continue;

            add(e[i],e[to]);

            in[e[to]]++;

        }

    queue<int> q;

    for(register int i=;i<=cnt;i++)

        if(!in[i])q.push(i);

    while(!q.empty())

    {

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

        for(register int i=first[x];i;i=eg[i].next)

        {

            int to=eg[i].v;

            t[to]|=t[x];

            in[to]--;

            if(!in[to])q.push(to);

        }

    }

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

        ans+=t[i].count()*len[i];

    printf("%d",ans);

}

BITSET：

我们借助c++STL解决问题，对于每个点建一个bitset;

bitset可以理解为一个加长的二进制数，普通二进制数的位运算bitset都能做，(&|~^>><<)

C++的 bitset 在 bitset 头文件中，它是一种类似数组的结构，它的每一个元素只能是０或１，每个元素仅用１bit空间。

定义：bitset<n>b//长度为n，名称为b的一个bitset

相关函数：

b.size() 返回大小（位数）

b.count() 返回1的个数

b.any() 返回是否有1

b.none() 返回是否没有1

b.set() 全都变成1

b.set(p) 将第p + 1位变成1

b.set(p, x) 将第p + 1位变成x

b.reset() 全都变成0

b.reset(p) 将第p + 1位变成0

b.flip() 全都取反

b.flip(p) 将第p + 1位取反

b.to_ulong() 返回它转换为unsigned long的结果，如果超出范围则报错

b.to_ullong() 返回它转换为unsigned long long的结果，如果超出范围则报错

b.to_string() 返回它转换为string的结果

至于它的时间复杂度，和电脑本身有关，一般来说是使复杂度/32

一段关于bitset的代码：

#include <cstdio>

#include <bitset>

#include <cstring>

#include <iostream>

#include <algorithm>

const int N=10;

std::bitset<N> a,b;//如果定义数组写成bitset<N> a[M];

int main(){

    puts("stage 0");

    std::cout<<a<<std::endl;

    std::cout<<b<<std::endl;

    a[1]=1;

    b[0]=1;

    puts("stage 1");

    std::cout<<a[1]<<std::endl;

    std::cout<<b[0]<<std::endl;

    std::cout<<a<<std::endl;

    std::cout<<b<<std::endl;

    a=a|b;//等效于a|=b

    puts("stage 2");

    std::cout<<a<<std::endl;

    a=a<<3;//等效于a<<=3

    puts("stage 3");

    std::cout<<a<<std::endl;

    a=a>>3;//等效于a>>=3

    puts("stage 4");

    std::cout<<a<<std::endl;

    a=a^b;//等效于a^=b

    puts("stage 5");

    std::cout<<a<<std::endl;

    a=a&b;//等效于a&=b;

    puts("stage 6");

    std::cout<<a<<std::endl;

    a.set();

    puts("stage 7");

    std::cout<<a<<std::endl;

    a.reset();

    puts("stage 8");

    std::cout<<a<<std::endl;

    a=~b;

    puts("stage 9");

    std::cout<<a<<std::endl;

    std::cout<<b<<std::endl;

    a[2]=0,a[5]=0;

    puts("stage 10");

    std::cout<<a<<std::endl;

    std::cout<<a.count()<<" "<<a.size()<<std::endl;

    b=a;

    puts("stage 11");

    std::cout<<b<<std::endl;

    a=5;

    puts("stage 12");

    std::cout<<a<<std::endl;

    return 0;

}

//时间复杂度，整体操作都是长度/32（64位机器除64），单个操作（操作单个位）是O(1)的

//空间复杂度，8位1字节，具体计算规则为在32位机器上Size = 4 * ((N + 31) / 32)在64位机器上Size = 8* ((N + 63) / 64)

    bitset<> foo ("");

    string s = foo.to_string();　　//将bitset转换成string类型

    unsigned long a = foo.to_ulong();　　//将bitset转换成unsigned long类型

    unsigned long long b = foo.to_ullong();　　//将bitset转换成unsigned long long类型

    cout << s << endl;　　//

    cout << a << endl;　　//

    cout << b << endl;　　//

     bitset<> foo ("");

     cout << foo.flip() << endl;　　//10011111　　（flip函数传参数时，用于将参数位取反，本行代码将foo下标２处"反转"，即０变１，１变０

     cout << foo.flip() << endl;　　 //01100000　　（flip函数不指定参数时，将bitset每一位全部取反

     cout << foo.set() << endl;　　　　//11111111　　（set函数不指定参数时，将bitset的每一位全部置为１

     cout << foo.set(,) << endl;　　//11110111　　（set函数指定两位参数时，将第一参数位的元素置为第二参数的值，本行对foo的操作相当于foo[3]=0

     cout << foo.set() << endl;　　  //11111111　　（set函数只有一个参数时，将参数下标处置为１

     cout << foo.reset() << endl;　　//11101111　　（reset函数传一个参数时将参数下标处置为０

     cout << foo.reset() << endl;　　 //00000000　　（reset函数不传参数时将bitset的每一位全部置为０

以上三段代码均来自大佬博客和题解（%%）

了解了bitset，我们要用它来解题了

b[i]表示一种状态，若b[i][j]=1，则表示有一条由i向j连的边（i也要和自己连边）

若i能到j，那么i也能到j所能到的点，那么直接b[i]|b[j]即能把状态转移：

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

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

            if(bit[i][j]) bit[i]|=bit[j];

这里一定是要j在外层，i在内层，原因博主还没有想通，有理解的欢迎在评论区留言

最后我们用bitset函数中的count()统计每个bitset中1的个数，然后输出答案

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

#include<vector>

#include<bitset>

#define MAXN 2005

using namespace std;

int n,ans=0;

bitset<MAXN>bit[MAXN];

char st[MAXN];

int main(){

    scanf("%d",&n);

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

        scanf("%s",st+1);

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

            if(st[j]=='1')

				bit[i][j]=1;

		bit[i][i]=1;

    }

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

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

            if(bit[i][j]) bit[i]|=bit[j];

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

        ans+=bit[i].count();

    printf("%d\n",ans);

    return 0;

}

巴特西

[JSOI2010]连通数（dfs或tarjan或bitset）+bitset学习

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

最新文章

热门文章

巴特西

[JSOI2010]连通数 （dfs或tarjan或bitset）+bitset学习

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

最新文章

热门文章

[JSOI2010]连通数（dfs或tarjan或bitset）+bitset学习