“C语言“ 之 特工的单向通信网络

       有一个由N位特工组成的情报网，为了防止暴露，特工之间建立了M条通信通路，每条通路只能单向传递信息，即一条从特工1到特工2的通路只能由1向2传递信息。信息可以中转，如下图所示，1发出的信息，可以通过2转发给4，也可以通过3转发给4。
　　由于保密的原因，并不是所有特工之间都互相知道彼此的存在。只有当两个特工之间可以直接或间接传递信息时，他们才彼此知道对方的存在。

       上图中给了一个4位特工的例子，图中的单向边表示通路。特工1可以将消息发送给所有部门，特工4可以接收所有部门的消息，所以特工1和特工4知道所有其他部门的存在。特工2和特工3之间没有任何方式可以发送消息，所以特工2和特工3互相不知道彼此的存在。
　　现在请问，有多少个特工知道所有N位特工的存在。或者说，有多少个特工知道的特工数量（包括自己）正好是N。

输入格式

　　输入的第一行包含两个整数N, M，分别表示特工的数量和单向通路的数量。所有特工从1到N标号。
　　接下来M行，每行两个整数a, b，表示特工a到特工b有一条单向通路。

输出格式

　　输出一行，包含一个整数，表示答案。

样例输入

4 4
    1 2
    1 3
    2 4
    3 4

样例输出

2

样例说明

　　特工1和特工4知道所有其他特工的存在。

 要求：

1. 假设问题规模为1 ≤ N ≤ 1000，1 ≤ M ≤ 100000，你会用什么样的数据结构存储数据？假设问题规模为1 ≤ N ≤ 1000，1 ≤ M ≤ 1000，你会用什么样的数据结构存储数据？请分别说明理由。
2. 假设问题规模为1 ≤ N ≤ 1000000，1 ≤ M ≤ 100000000000，你会用什么样的数据结构存储数据？请说明理由。
3. 假设问题规模为1 ≤ N ≤ 1000000，1 ≤ M ≤ 100000000000，用伪代码写出你为本题设计的算法，并解释为什么选择这种算法，分析出该算法的时间复杂度。
4. 编程实现你的算法，给出程序代码，加上详细注释。给出程序运行截图

1. 假设问题规模为1 ≤ N ≤ 1000，1 ≤ M ≤ 100000，你会用什么样的数据结构存储数据？假设问题规模为1 ≤ N ≤ 1000，1 ≤ M ≤ 1000，你会用什么样的数据结构存储数据？请分别说明理由。

      答：如果N属于1到1000之间M在1到100000之间我会用邻接表，如果是N属于1到1000,M属于1到1000之间我会用邻接矩阵存储。 如果用邻接矩阵来遍历，邻接矩阵用起来比较方便，而且比较容易理解，N和M在这个数据范围是比较可以的，实用于邻接矩阵的使用范围，邻接矩阵的数字的内存也没有超出范围造成内存不足，使源代码因为内存不足而造成运行时错误，但是，这样对于边数相对顶点较少的图，这种结构对储存空间的极大的浪费。用邻接矩阵会比较直观，比较简单方便检查任意一顶点的所有“邻接点”方便计算任一顶点的“度。但是邻接表在稀疏图中有大量无效元素。也可以用邻接表来实现结构存储数据，因为邻接表的的建立不用担心内存不足造成的数据存储崩溃从而造成运行错误，邻接表的运用需要比较节省空间而且不会出现空间储存超出范围。两者的区别邻接表一般用于稀疏图而邻接矩阵用于稠密图较多，因为邻接表是你可以不断申请空间，需要多少可以申请多少空间，而邻接矩阵的空间是固定的，从而会造成稀疏图的空间浪费。而且邻接表不方便检查任意一对应点之间是否存在边。

      2.假设问题规模为1 ≤ N ≤ 1000000，1 ≤ M ≤ 100000000000，你会用什么样的数据结构存储数据？请说明理由。(10分)

       答：如果N在1到1000000之间，M在1到10000000000之间，我会用邻接表，因为N,M的数据最大值太大，建立不了邻接矩阵，如果用邻接矩阵会出现数据溢出造成储存数据崩溃，从而使程序崩溃。而如果用邻接表就不会出现内存空间不足造成数据储存崩溃，因为邻接表你可以随时申请空间，从而不会造成空间储存的崩溃。而且一般这样的图都是稀疏图，所以用邻接矩阵会造成空间大量浪费，所以用邻接表比较好，因为数据过大，用邻接矩阵也就不会那么直观，那么清晰的反应出来数据，所以用邻接表要更好。

      3.假设问题规模为1 ≤ N ≤ 1000000，1 ≤ M ≤ 100000000000，用伪代码写出你为本题设计的算法，并解释为什么选择这种算法，分析出该算法的时间复杂度。

       答:先建立一个邻接表。adjlist

         建立一个拜访数组。visited

         建立一个储存信息传递人数的数组还有一个信息接收人数的数组,a,b

         输入总人数和传递信息的边数。N,M

         记录特工都知道的总个数k;

         分别为邻接表adjlist,拜访数组visited,储存信息传递人数的数组a,信息接收人数的数组b申请空间并初始化

        开始建立有向图的邻接表；

        然后分别对从1开始到N结束进行深度优先遍历，并记录接受和信息传递的数，每次从不同的数进行深度优先遍历，都要初始化拜访数组visited,

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

    {

        DFS//进行深度优先搜索

  {

如果拜访的数组visited等于1就返回

       每次接收信息就b[x]加一

        每次发送信息把第j次的发送信息加1

    标记拜访过，就把拜访过的数组visited[x]赋值为1

    定义一个链表p为x的访问链表adjlist[x];

    当p不为空时进行深搜

    {

        对p对应的值进行深搜

        让p指向下一个数

    }//遍历}

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

    {

    }//初始化拜访数组用于下次遍历

    }

       最后进行对储存信息传递人数的数组a,信息接收人数的数组b中所有为N的数进行记录，每记录1个k都要加一最后进行输出。

      为什么要使用这个算法，因为在这个有向图的问题中如果我们想要知道，接受信息的人数必须要根据方向找到接收信息的人所以要进行深度优先遍历找到接收信息的人，但是要知道谁发送信息所以必须要对每一个都进行深度优先搜索找到发送信息的人。所以要用深度优先遍历进行搜索。并且要对每一个数都进行深搜，并进行记录。

     这个算法的时间复杂度为O(N^2)

    因为深度优先遍历的时间复杂度为1,因为要对不同的数都要进行深度优先搜索所以时间复杂度为O(N),但是每一次都要初始化拜访数组visited，每一次初始化的时间复杂度为O(N),所以N个数的时间复杂度为O(N^2)所以总的时间复杂度为O(N^2)。

     4.编程实现你的算法，给出程序代码，加上详细注释。给出程序运行截图

       答：

#include

#include



typedef struct _edge

{

    int data;

    struct _edge *next;

}edge;//建立链表



edge **adjlist;//建立一个邻接表

int *visited;//建立一个拜访数组

int N,M;//N，M分别表示顶点数和边数，

int *a;

int *b;

void DFS(int x,int L);



int main(void)

{

    int k=0;//k用来表示都知道特工存在的个数，

    scanf("%d%d",&N,&M);//输入顶点和边数



    visited=(int*)malloc((N+1)*sizeof(int));//用来申请空间储存拜访过的数

    adjlist=(edge**)malloc((N+1) * sizeof(edge*));//用来申请建立邻表的空间

    a=(int*)malloc((N+1)*sizeof(int));

    b=(int*)malloc((N+1)*sizeof(int));//用来申请空间，用来储存发出信息知道的人数和接收信息知道的人数

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

    {

        adjlist[i]=NULL;

        visited[i]=0;

        a[i]=0;

        b[i]=0;

    }//初始拜访数组，和邻接表,

    for(int i=0;idata=w;

        t->next=adjlist[v];

        adjlist[v]=t;//建立邻接表



    }

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

    {

        DFS(j,j);//进行深度优先搜索

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

    {

        visited[i]=0;

    }//初始化邻接表用于下次遍历

    }

    for(int i=1;idata,L);

        p=p->next;

    }//遍历

}

运行截图：