亚线性时间算法求连通分量

要求

自己给出ϵ的值并带入计算

简述算法过程

先用一个队列，建立一个广度搜索树，取样，则n/(取样倒数和)
同一个连通分量中的每一个点的 1 /n v是一样的，都是分量中点的个数的倒数
就是一个小型的搜索，如果搜索到的点的个数小于 2/ ϵ ​就继续搜索，否则直接返回 2/ ϵ ​

代码

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <queue>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define QueueSize 50

class Env
{
public:
    vector<vector<int>> graph;
    Env()
    {
        graph = getGraph("rand2_2.csv"); //rand1_1.csv rand1_2.csv rand1_3.csv rand2_1.csv rand2_2.csv 共5个测试用例
    }

    vector<vector<int>> getGraph(string file_path)
    {
        vector<vector<int>> user_arr;
        ifstream fp(file_path);
        string line;
        while (getline(fp, line))
        {
            vector<int> data_line;
            string number;
            istringstream readstr(line);
            for (int j = 0; j < 20; j++)
            {
                getline(readstr, number, ',');
                data_line.push_back(atoi(number.c_str()));
            }
            user_arr.push_back(data_line);
        }
        return user_arr;
    }
};

// 所有的代码都需要写在 Algo 类内，自行定义其他需要的变量或函数
class Algo
{
public:
    Algo()
    {
        cout << "algo ok" << endl;
    }

    typedef struct
    {
        int front;
        int rear;
        int count;
        int data[QueueSize];
    } Queue;

    void InitQueue(Queue *M)
    {
        M->front = M->rear = 0;
        M->count = 0;
    }

    int QueueEmpty(Queue *M) 
    {
        if (M->count == 0)
            return 1;
        else
            return 0;
    }

    void EnQueue(Queue *M, int x) 
    {
        M->count++;
        M->data[M->rear] = x;
        M->rear = (M->rear + 1) % QueueSize;
    }

    int DeQueue(Queue *M) 
    {
        int temp;
        temp = M->data[M->front];
        M->count--;
        M->front = (M->front + 1) % QueueSize;
        return temp;
    }

    int run(Env env)
    {
        //在此写入你的代码  env.graph 为目标矩阵
        Queue M;
        InitQueue(&M);
        double p = 0.1;
        double q[11];
        double a;
        a = 2 / p;
        srand((unsigned)time(NULL));
        for (int k = 1; k < 11; k++) 
        {
            InitQueue(&M);
            int visited[20];
            for (int m = 0; m < 20; m++)
                visited[m] = 0;
            int i = rand() % 20;
            visited[i] = 1;
            EnQueue(&M, i);
            double t = 1;
            while (!QueueEmpty(&M))
            {
                i = DeQueue(&M);
                for (int j = 0; j < 20; j++)
                {
                    if (double(j) <= double(a))
                    {
                        if (env.graph[i][j] != 0 && visited[j] == 0)
                        {
                            t = double(t + 1);
                            visited[j] = 1;
                            EnQueue(&M, j);
                        }
                    }
                }
            }

            if (t != 0)
            {
                q[k] = double(1 / t);
            }
            else
            {
                q[k] = 0;
            }
        }
        double sum;
        for (int k = 1; k < 11; k++)
        {
            sum = q[k] + sum;
        }
        sum = sum / 10 * 20;
        cout << sum << endl;

        return 0; //修改为返回正确的结果
    }
};

int main()
{
    Algo algo;
    Env env;
    time_t start = clock();
    algo.run(env);
    time_t end = clock();
    cout << "程序耗时: " << double(end - start) / CLOCKS_PER_SEC << " ms" << endl;
    cout << "占用内存：" << sizeof(algo) << " byte" << endl;
    return 0;
}

结果