数据结构中的无向图,用C语言实现的过程中的思路???

roblem Description
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

There is an undirected graph with n vertices and m edges. Then Yuta does q operations on this graph. Each operation is described by two integers L,R (1≤L≤R≤n) and can be split into three steps:

  1. Delete all the edges which have at least one vertice outside the range [L,R].

  2. Yuta wants you to tell him the number of connected component of the graph.

  3. Restore the graph.

This task is too hard for Rikka to solve. Can you help her?

Input
There are at most 100 testcases and there are at least 97 testcases with n,m,q≤1000.

For each testcase, the first line contains three numbers n,m,q (n,q≤105,m≤2×105).

Then m lines follow. Each line contains two numbers ui,vi (1≤ui,vi≤105) which describe an edge of the graph.

Then q lines follows. Each line contains two numbers Li,Ri (1≤L≤R≤n) which describe an operation.

Output
For each operation you need print a single line with a single number - the answer of this operation.

Sample Input
3 3 2
1 2
1 3
2 3
1 2
1 3

Sample Output
2
1

2个回答

图有一种邻接表储存结构,这里以无向图为例,输入图的参数,构造并输出图的邻接表。

#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 100
typedef struct ArcNode{
    int adjvex;//该边的另一个顶点的位置 
    struct ArcNode *nextarc; //指向下一条边 
}ArcNode;
typedef struct VNode{
    int data;//顶点的值 
    ArcNode *firstarc;//指向第一条依附该顶点的边的指针 
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
    AdjList vertices;//顶点数组 
    int vexnum,arcnum;
}ALGraph;
int LocateVex(ALGraph G,int v){//定位函数 
    for(int i=0;i<G.vexnum;i++){
        if(v==G.vertices[i].data)return i;
    } 
}
void CreateUDG(ALGraph &G){
    ArcNode *p,*q;
    int i,j,k,v1,v2;
    printf("分别输入顶点个数和边的数目:\n");
    scanf("%d%d",&G.vexnum,&G.arcnum);
    printf("分别输入各个顶点值:\n");
    for(i=0;i<G.vexnum;i++){
    scanf("%d",&G.vertices[i].data);
    G.vertices[i].firstarc=NULL;//初始化 
    } 
    printf("分别输入各条边的两个顶点:\n");
    for(k=0;k<G.arcnum;k++){
        scanf("%d%d",&v1,&v2);
        i=LocateVex(G,v1);j=LocateVex(G,v2);//定位 
        p=(ArcNode*)malloc(sizeof(ArcNode));//申请一个结点 
        p->adjvex=j;p->nextarc=NULL;//赋值 
        p->nextarc=G.vertices[i].firstarc;//连接结点 
        G.vertices[i].firstarc=p;//连接结点 
        q=(ArcNode*)malloc(sizeof(ArcNode));
        q->adjvex=i;q->nextarc=NULL;
        q->nextarc=G.vertices[j].firstarc;
        G.vertices[j].firstarc=q;
    }
}
void PrintUDG(ALGraph G){//输出邻接表 
    int i,j;
    for(i=0;i<G.vexnum;i++){
        printf("%d:",i);
        ArcNode *p;
        p=G.vertices[i].firstarc;
        while(p!=NULL){
            printf("->%d",p->adjvex);
            p=p->nextarc;
        }
        printf("\n");
    }
}
int main(){
    ALGraph G;
    CreateUDG(G);
    PrintUDG(G);
    return 0;
}

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

1
C语言的数据结构的连通图的问题,用C语言怎么编写代码去实现?
1
数据结构,无向图的遍历求解,判断其中的环,用C语言怎么实现的??
0
一个无向图的计算的顶点的数据结构问题的算法表示,采用C语言进行计算
1
数据结构C++ 社交网络图的实现 设计并实现一种简单的社交网络模型图。
0
拥有N个定点的无向图的一个算法的问题,采用C语言的程序设计思路的办法来怎么解决的
0
一个图的搜索的数据结构组织的问题,用C程序设计的语言实现的方式
0
连通图的稳定状态的计算用的数据结构,怎么采用C程序语言的编程算法的实现的过程
0
数据结构上的图节点的一个遍历的问题怎么采用C程序的语言代码的解决的过程怎么实现?
1
求一个代码c语言实现图的深度遍历(递归)、非递归算法以及实现图的广度遍历(队列)
1
c语言,建立无向图进行广度优先遍历产生问题
0
C语言数据结构难题,求大佬解答,万分感谢!!!
2
如何用kettle实现比较源数据库中的所有表数据和目标数据库中的对应的表数据是否一致
2
用STM32-F4,C语言实现交通灯控制系统设计,这个怎么办呢?有大神提供思路和代码吗?
0
求助!C语言栈数据结构关于栈的问题
1
求助大神,关于C语言数据结构中栈的问题
3
关与c语言中结构体typedef的用法
0
如何向C#winform中的chart图以表格的形式加数据
2
关于c语言数据传参的问题
3
关于C语言中的结构体。
0
用邻接矩阵创建有向网,求最小生成树,最短路径(c语言)。