C语言的数据结构的连通图的问题,用C语言怎么编写代码去实现?

Problem Description
众所周知,度度熊喜欢图,尤其是联通的图。

今天,它在图上又玩出了新花样,新高度。有一张无重边的无向图, 求有多少个边集,使得删掉边集里的边后,图里恰好有K个连通块。

Input
第一行为T,表示输入数据组数。

对于每组数据,第一行三个整数N,M,K,表示N个点M条边的图。
接下来M行每行两个整数a,b,表示点a和点b之间有一条边。

1≤T≤20

1≤K≤N≤14

0≤M≤N∗(N+1)/2
1≤a,b≤N

Output
对第i组数据,输出

Case #i:

然后输出一行,仅包含一个整数,表示方法种数(对 1 000 000 009 取模) 。

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

Sample Output
Case #1:
1
Case #2:
2
Case #3:
3

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
如何用c语言来判断邻接矩阵是否连通的代码
如何用c语言来判断邻接矩阵是否连通的代码 判断所给的图是否为连通图。 实验用例:邻接矩阵A1=0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0
连通图的环的判断问题数据结构的设计,怎么利用C语言的编写形式?
Problem Description Recently, scientists find that there is love between any of two people. For example, between A and B, if A don’t love B, then B must love A, vice versa. And there is no possibility that two people love each other, what a crazy world! Now, scientists want to know whether or not there is a “Triangle Love” among N people. “Triangle Love” means that among any three people (A,B and C) , A loves B, B loves C and C loves A. Your problem is writing a program to read the relationship among N people firstly, and return whether or not there is a “Triangle Love”. Input The first line contains a single integer t (1 <= t <= 15), the number of test cases. For each case, the first line contains one integer N (0 < N <= 2000). In the next N lines contain the adjacency matrix A of the relationship (without spaces). Ai,j = 1 means i-th people loves j-th people, otherwise Ai,j = 0. It is guaranteed that the given relationship is a tournament, that is, Ai,i= 0, Ai,j ≠ Aj,i(1<=i, j<=n,i≠j). Output For each case, output the case number as shown and then print “Yes”, if there is a “Triangle Love” among these N people, otherwise print “No”. Take the sample output for more details. Sample Input 2 5 00100 10000 01001 11101 11000 5 01111 00000 01000 01100 01110 Sample Output Case #1: Yes Case #2: No
一个数据结构有关连通图生成算法的一个问题,用C语言怎么解决这个问题?
Problem Description 《Dream of the Red Chamber》(also 《The Story of the Stone》) is one of the Four Great Classical Novels of Chinese literature, and it is commonly regarded as the best one. This novel was created in Qing Dynasty, by Cao Xueqin. But the last 40 chapters of the original version is missing, and that part of current version was written by Gao E. There is a heart breaking story saying that after Cao Xueqin died, Cao's wife burned the last 40 chapter manuscript for heating because she was desperately poor. This story was proved a rumor a couple of days ago because someone found several pages of the original last 40 chapters written by Cao. In the novel, Wang Xifeng was in charge of Da Guan Yuan, where people of Jia family lived. It was mentioned in the newly recovered pages that Wang Xifeng used to arrange rooms for Jia Baoyu, Lin Daiyu, Xue Baochai and other teenagers. Because Jia Baoyu was the most important inheritor of Jia family, and Xue Baochai was beautiful and very capable , Wang Xifeng didn't want Jia Baoyu to marry Xue Baochai, in case that Xue Baochai might take her place. So, Wang Xifeng wanted Baoyu's room and Baochai's room to be located at two ends of a road, and this road should be as long as possible. But Baoyu was very bad at directions, and he demanded that there could be at most one turn along the road from his room to Baochai's room, and if there was a turn, that turn must be ninety degree. There is a map of Da Guan Yuan in the novel, and redists (In China English, one whose job is studying 《Dream of the Red Chamber》is call a "redist") are always arguing about the location of Baoyu's room and Baochai's room. Now you can solve this big problem and then become a great redist. Input The map of Da Guan Yuan is represented by a matrix of characters '.' and '#'. A '.' stands for a part of road, and a '#' stands for other things which one cannot step onto. When standing on a '.', one can go to adjacent '.'s through 8 directions: north, north-west, west, south-west, south, south-east,east and north-east. There are several test cases. For each case, the first line is an integer N(0<N<=100) ,meaning the map is a N × N matrix. Then the N × N matrix follows. The input ends with N = 0. Output For each test case, print the maximum length of the road which Wang Xifeng could find to locate Baoyu and Baochai's rooms. A road's length is the number of '.'s it includes. It's guaranteed that for any test case, the maximum length is at least 2. Sample Input 3 #.# ##. ..# 3 ... ##. ..# 3 ... ### ..# 3 ... ##. ... 0 Sample Output 3 4 3 5
连通图数据结构上面的一个路径的搜索的算法问题,采用C语言的程序的设计的办法
Problem Description Scofield is a hero in American show "Prison Break". He had broken the prison and started a big runaway. Scofield has a map of US with cities and bidirectional roads between them. The lengths of roads are known. Some cities get a lot of cops who are very troublesome. Now Scofield needs your help to arrange his runaway route. He needs a shortest path between two cities, while the quantity of the police in any city, except the start city and end city, on the route is no more than k. You should know that it is very hard to escape. Scofield is very smart but not good at computer. Now Scofield is in trouble, can you help him with your computer? Input The input consists of several test cases. There is an integer T on the first line indicating the number of test cases. For each case, the first line consists of two integers N and M. N is the number of cities; M is the number of roads. The next line contains N integers C1, C2... CN, where Ci is the number of cops in city i. Then followed M lines, each line consists of three integer, u, v, w, indicating there is a road with length w between city u and city v. The following line consists of an integer Q, indicating the number of queries. Each of the following Q lines consists of three integers, u, v, k, indicating the query for the shortest path between city u and city v with limitation of k cops. Technical Specification 1. T ≤ 20 2. 2 ≤ N ≤ 200, 0 ≤ M ≤ n * (n – 1) / 2 3. 0 ≤ Ci ≤ 1000,000,000 4. 0 ≤ u, v < N, 0 ≤ w ≤ 1000, 0 ≤ k ≤ 1000,000,000 5. 0 ≤ Q ≤ 100000 6. There is no more than ONE road between two cities and no road between the same cities. 7. For each query, u is not equal to v. 8. There is ONE empty line after each test case. Output For each query, output a single line contains the length of the shortest path. Output "-1" if you can't find the path. Please output an empty line after each test case. Sample Input 1 4 4 100 2 3 100 0 1 1 0 2 1 1 3 2 2 3 3 2 0 3 2 0 3 1 Sample Output 3 -1
连通图的数据结构上的一个算法的视线,怎么能采用C语言的程序的设计的思想去实现?
Problem Description Betty owns a lot of ponds, some of them are connected with other ponds by pipes, and there will not be more than one pipe between two ponds. Each pond has a value v. Now Betty wants to remove some ponds because she does not have enough money. But each time when she removes a pond, she can only remove the ponds which are connected with less than two ponds, or the pond will explode. Note that Betty should keep removing ponds until no more ponds can be removed. After that, please help her calculate the sum of the value for each connected component consisting of a odd number of ponds Input The first line of input will contain a number T(1≤T≤30) which is the number of test cases. For each test case, the first line contains two number separated by a blank. One is the number p(1≤p≤104) which represents the number of ponds she owns, and the other is the number m(1≤m≤105) which represents the number of pipes. The next line contains p numbers v1,...,vp, where vi(1≤vi≤108) indicating the value of pond i. Each of the last m lines contain two numbers a and b, which indicates that pond a and pond b are connected by a pipe. Output For each test case, output the sum of the value of all connected components consisting of odd number of ponds after removing all the ponds connected with less than two pipes. Sample Input 1 7 7 1 2 3 4 5 6 7 1 4 1 5 4 5 2 3 2 6 3 6 2 7 Sample Output 21
C语言求可达矩阵,判断图的连通性
怎样用C语言表示邻接矩阵求可达矩阵,并且判断图的连通性,急,谢谢帮忙
连通图的稳定状态的计算用的数据结构,怎么采用C程序语言的编程算法的实现的过程
Problem Description Rasen had lost in labyrinth for 20 years. In a normal day, he found a bright screen. There were 4 points labeled by ‘A’ , ‘B’ , ‘C’ , ‘D’, and rasen could drag these point. And two points ‘E’ , ‘F’ moved. Rasen found that ‘E’ is the middle point of ‘A’ and ‘B’, and ‘F’ is the middle point of ‘C’ and ‘D’. Near the screen there was a marble slab.There were a list of the distance of AB , BC , CD , DA and EF. Rasen also found that the distance of these edge of the points in screen showed at the same time he drop the points. He wanted to know what will happen if the distances in screen are same with the number in slab. Input The first line of input contains only one integer T(<=50000), the number of test cases. Each case contains five float number, indicating the distance of AB , BC , CD , DA , EF.(0<=distance<=10000) Output For each test, first print a line “Case #i:”(without quotes),with i implying the case number, then output the coordinates of A,B,C,D four points. Answer will be considered as correct if the length got from your output (the spj will use double to get the point, and the distance from two points will calculate in the way of sqrt((x1-x2)^2 +(y1-y2)^2) ) and the length given is less than 10-4. (It guarantees that there exists a solution. If there are many solutions, output any one of them.) Sample Input 1 1.000000 1.000000 1.000000 1.000000 1.000000 Sample Output Case #1: 0.000000 0.000000 1.000000 0.000000 1.000000 1.000000 0.000000 1.000000
8个节点的连通图矩阵怎么用C语言的程序的编写设计的过程方式有效实现的思维是什么
Problem Description Fill the following 8 circles with digits 1~8,with each number exactly once . Conntcted circles cannot be filled with two consecutive numbers. There are 17 pairs of connected cicles: A-B , A-C, A-D B-C, B-E, B-F C-D, C-E, C-F, C-G D-F, D-G E-F, E-H F-G, F-H G-H Filling G with 1 and D with 2 (or G with 2 and D with 1) is illegal since G and D are connected and 1 and 2 are consecutive .However ,filling A with 8 and B with 1 is legal since 8 and 1 are not consecutive . In this problems,some circles are already filled,your tast is to fill the remaining circles to obtain a solution (if possivle). Input The first line contains a single integer T(1≤T≤10),the number of test cases. Each test case is a single line containing 8 integers 0~8,the numbers in circle A~H.0 indicates an empty circle. Output For each test case ,print the case number and the solution in the same format as the input . if there is no solution ,print “No answer”.If there more than one solution,print “Not unique”. Sample Input 3 7 3 1 4 5 8 0 0 7 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 Sample Output Case 1: 7 3 1 4 5 8 6 2 Case 2: Not unique Case 3: No answer
连通的图的计算表达问题,要求使用C语言来实现
Problem Description Once there was a special graph. This graph had n vertices and some edges. Each edge was either white or black. There was no edge connecting one vertex and the vertex itself. There was no two edges connecting the same pair of vertices. It is special because the each vertex is connected to at most two black edges and at most two white edges. One day, the demon broke this graph by copying all the vertices and in one copy of the graph, the demon only keeps all the black edges, and in the other copy of the graph, the demon keeps all the white edges. Now people only knows there are w0 vertices which are connected with no white edges, w1 vertices which are connected with 1 white edges, w2 vertices which are connected with 2 white edges, b0 vertices which are connected with no black edges, b1 vertices which are connected with 1 black edges and b2 vertices which are connected with 2 black edges. The precious graph should be fixed to guide people, so some people started to fix it. If multiple initial states satisfy the restriction described above, print any of them. Input The first line of the input is a single integer T (T≤700), indicating the number of testcases. Each of the following T lines contains w0,w1,w2,b0,b1,b2. It is guaranteed that 1≤w0,w1,w2,b0,b1,b2≤2000 and b0+b1+b2=w0+w1+w2. It is also guaranteed that the sum of all the numbers in the input file is less than 300000. Output For each testcase, if there is no available solution, print −1. Otherwise, print m in the first line, indicating the total number of edges. Each of the next m lines contains three integers x,y,t, which means there is an edge colored t connecting vertices x and y. t=0 means this edge white, and t=1 means this edge is black. Please be aware that this graph has no self-loop and no multiple edges. Please make sure that 1≤x,y≤b0+b1+b2. Sample Input 2 1 1 1 1 1 1 1 2 2 1 2 2 Sample Output -1 6 1 5 0 4 5 0 2 4 0 1 4 1 1 3 1 2 3 1
数据结构的图论方面的问题,求这个图上的边的个数的和,要运用C语言技术
Problem Description 我们建造了一个大项目!这个项目有n个节点,用很多边连接起来,并且这个项目是连通的! 两个节点间可能有多条边,不过一条边的两端必然是不同的节点。 每个节点都有一个能量值。 现在我们要编写一个项目管理软件,这个软件呢有两个操作: 1.给某个项目的能量值加上一个特定值。 2.询问跟一个项目相邻的项目的能量值之和。(如果有多条边就算多次,比如a和b有2条边,那么询问a的时候b的权值算2次)。 Input 第一行一个整数T(1 <= T <= 3),表示测试数据的个数。 然后对于每个测试数据,第一行有两个整数n(1 <= n <= 100000)和m(1 <= m <= n + 10),分别表示点数和边数。 然后m行,每行两个数a和b,表示a和b之间有一条边。 然后一个整数Q。 然后Q行,每行第一个数cmd表示操作类型。如果cmd为0,那么接下来两个数u v表示给项目u的能量值加上v(0 <= v <= 100)。 如果cmd为1,那么接下来一个数u表示询问u相邻的项目的能量值之和。 所有点从1到n标号。 Output 对每个询问,输出一行表示答案。 Sample Input 1 3 2 1 2 1 3 6 0 1 15 0 3 4 1 1 1 3 0 2 33 1 2 Sample Output 4 15 15
连通图上的距离的搜索的问题,怎么利用C语言的程序的设计的方式实现的呢
Problem Description Matt has N friends. They are playing a game together. Each of Matt’s friends has a magic number. In the game, Matt selects some (could be zero) of his friends. If the xor (exclusive-or) sum of the selected friends’magic numbers is no less than M , Matt wins. Matt wants to know the number of ways to win. Input The first line contains only one integer T , which indicates the number of test cases. For each test case, the first line contains two integers N, M (1 ≤ N ≤ 40, 0 ≤ M ≤ 106). In the second line, there are N integers ki (0 ≤ ki ≤ 106), indicating the i-th friend’s magic number. Output For each test case, output a single line “Case #x: y”, where x is the case number (starting from 1) and y indicates the number of ways where Matt can win. Sample Input 2 3 2 1 2 3 3 3 1 2 3 Sample Output Case #1: 4 Case #2: 2
二维字符连通图的问题,运用C语言的知识的综合理解的实现
Problem Description Bob Bennett, the young adventurer, has found the map to the treasure of the Chimp Island, where the ghost zombie pirate LeChimp, the infamous evil pirate of the Caribbeans has hidden somewhere inside the Zimbu Memorial Monument (ZM2). ZM2 is made up of a number of corridors forming a maze. To protect the treasure, LeChimp has placed a number of stone blocks inside the corridors to block the way to the treasure. The map shows the hardness of each stone block which determines how long it takes to destroy the block. ZM2 has a number of gates on the boundary from which Bob can enter the corridors. Fortunately, there may be a pack of dynamites at some gates, so that if Bob enters from such a gate, he may take the pack with him. Each pack has a number of dynamites that can be used to destroy the stone blocks in a much shorter time. Once entered, Bob cannot exit ZM2 and enter again, nor can he walk on the area of other gates (so, he cannot pick more than one pack of dynamites). The hardness of the stone blocks is an integer between 1 and 9, showing the number of days required to destroy the block. We neglect the time required to travel inside the corridors. Using a dynamite, Bob can destroy a block almost immediately, so we can ignore the time required for it too. The problem is to find the minimum time at which Bob can reach the treasure. He may choose any gate he wants to enter ZM2. Input The input consists of multiple test cases. Each test case contains the map of ZM2 viewed from the above. The map is a rectangular matrix of characters. Bob can move in four directions up, down, left, and right, but cannot move diagonally. He cannot enter a location shown by asterisk characters (*), even using all his dynamites! The character ($) shows the location of the treasure. A digit character (between 1 and 9) shows a stone block of hardness equal to the value of the digit. A hash sign (#) which can appear only on the boundary of the map indicates a gate without a dynamite pack. An uppercase letter on the boundary shows a gate with a pack of dynamites. The letter A shows there is one dynamite in the pack, B shows there are two dynamite in the pack and so on. All other characters on the boundary of the map are asterisks. Corridors are indicated by dots (.). There is a blank line after each test case. The width and the height of the map are at least 3 and at most 100 characters. The last line of the input contains two dash characters (--). Output For each test case, write a single line containing a number showing the minimum number of days it takes Bob to reach the treasure, if possible. If the treasure is unreachable, write IMPOSSIBLE. Sample Input *****#********* *.1....4..$...* *..***..2.....* *..2..*****..2* *..3..******37A *****9..56....* *.....******..* ***CA********** ***** *$3** *.2** ***#* -- Sample Output 1 IMPOSSIBLE
连通图上的点的可达性的判断的算法问题,怎么利用C语言的程序的设计的方式来实现的?
Problem Description Bob Bennett, the young adventurer, has found the map to the treasure of the Chimp Island, where the ghost zombie pirate LeChimp, the infamous evil pirate of the Caribbeans has hidden somewhere inside the Zimbu Memorial Monument (ZM2). ZM2 is made up of a number of corridors forming a maze. To protect the treasure, LeChimp has placed a number of stone blocks inside the corridors to block the way to the treasure. The map shows the hardness of each stone block which determines how long it takes to destroy the block. ZM2 has a number of gates on the boundary from which Bob can enter the corridors. Fortunately, there may be a pack of dynamites at some gates, so that if Bob enters from such a gate, he may take the pack with him. Each pack has a number of dynamites that can be used to destroy the stone blocks in a much shorter time. Once entered, Bob cannot exit ZM2 and enter again, nor can he walk on the area of other gates (so, he cannot pick more than one pack of dynamites). The hardness of the stone blocks is an integer between 1 and 9, showing the number of days required to destroy the block. We neglect the time required to travel inside the corridors. Using a dynamite, Bob can destroy a block almost immediately, so we can ignore the time required for it too. The problem is to find the minimum time at which Bob can reach the treasure. He may choose any gate he wants to enter ZM2. Input The input consists of multiple test cases. Each test case contains the map of ZM2 viewed from the above. The map is a rectangular matrix of characters. Bob can move in four directions up, down, left, and right, but cannot move diagonally. He cannot enter a location shown by asterisk characters (*), even using all his dynamites! The character ($) shows the location of the treasure. A digit character (between 1 and 9) shows a stone block of hardness equal to the value of the digit. A hash sign (#) which can appear only on the boundary of the map indicates a gate without a dynamite pack. An uppercase letter on the boundary shows a gate with a pack of dynamites. The letter A shows there is one dynamite in the pack, B shows there are two dynamite in the pack and so on. All other characters on the boundary of the map are asterisks. Corridors are indicated by dots (.). There is a blank line after each test case. The width and the height of the map are at least 3 and at most 100 characters. The last line of the input contains two dash characters (--). Output For each test case, write a single line containing a number showing the minimum number of days it takes Bob to reach the treasure, if possible. If the treasure is unreachable, write IMPOSSIBLE. Sample Input *****#********* *.1....4..$...* *..***..2.....* *..2..*****..2* *..3..******37A *****9..56....* *.....******..* ***CA********** ***** *$3** *.2** ***#* -- Sample Output 1 IMPOSSIBLE
广度优先搜索树 非连通图的遍历
在数据结构教程里,有一章是实现广度优先遍历非联通图,然后把遍历的图的节点 存在树的结构里,树的储存方式是孩子兄弟表示法。当我运行代码后,输入 了图的节点和节点之间的关系: 13,13 1 2 3 4 5 6 7 8 9 10 11 12 13 1,2 1,3 1,6 1,12 2,13 4,5 7,8 7,10 7,9 8,10 11,12 11,13 12,13 该有的结果应该是: 1 2 13 3 6 12 11 4 5 7 8 9 10 可我运行的结果是123 \n 456,也就是说function BFSForest根本没有被执行。 哪位大神可以帮我看看问题出在哪,谢谢! 以下是我的代码。 ``` #include <stdio.h> #include <stdlib.h> #define MAX_VER_NUM 20 //图的最大节点数 #define VRTYPE int //弧的类型 #define VertexType int //节点类型 typedef enum {false,true} bool; bool visited[MAX_VER_NUM]; typedef struct { VRTYPE adj; }adjMatrix[MAX_VER_NUM][MAX_VER_NUM];//图的邻接矩阵 typedef struct { VertexType ver[MAX_VER_NUM]; adjMatrix arcs; int num_vex,num_arcs; }MGraph;//图的结构体 typedef struct { VertexType data; struct gNode* lchild; struct gNode* nextsibling; }gNode;//生成树的节点,用孩子兄弟表示法 typedef struct { struct QueueCell *next; gNode *node; }QueueCell;//队列的节点 typedef struct { QueueCell *top; QueueCell *tail; }Queue;//定义队列的结构体 void initQueue(Queue **q) { if(!*q) { *q=(Queue*)malloc(sizeof(Queue)); (*q)->top=(QueueCell*)malloc(sizeof(QueueCell)); (*q)->top->next=NULL; (*q)->top->node=NULL; (*q)->tail=(*q)->top;//空队列头和尾巴在一起 } } int isEmpty(Queue *q) { if(q->tail==q->top)//空队列头和尾巴在一起 { return 1; } return 0;//如果判定结果为错,必须返回0,而不能是-1 } void EnQueue(Queue **q,gNode *g) { if(isEmpty(*q))//当队列为空时,头指针的next指针指向进队的节点 { QueueCell *c=(*q)->top->next; c->node=g; (*q)->tail=c; } else//如果队列不为空,头指针不变,更新尾巴 { QueueCell *c=(*q)->tail->next; c->node=g; (*q)->tail=c; } } gNode* DeQueue(Queue **q) { QueueCell *c=(*q)->top->next; (*q)->top->next= c->next; if(!(c->next))//出队后,队列为空时,尾巴重新指向头结点 { (*q)->tail=(*q)->top; } return c->node; } int locateVex(MGraph *G,VertexType v) { for(int i=0;i<G->num_vex;i++) { if(G->ver[i]==v) { return i; } } return -1; } void createGraph(MGraph *G) { scanf("%d,%d",&(G->num_vex),&(G->num_arcs));//输入图的节点数和弧的数量 for(int i=0;i<G->num_vex;i++) { scanf("%d",&(G->ver[i]));//输入图每个节点的值 } for(int i=0;i<G->num_vex;i++)//初始化邻接矩阵 { for(int j=0;j<G->num_vex;j++) { G->arcs[i][j].adj=0; } } for(int i=0;i<G->num_arcs;i++)//更新邻接矩阵 { VertexType v1,v2; scanf("%d,%d",&v1,&v2); int n1=locateVex(G,v1); int n2=locateVex(G,v2); if(n1==-1||n2==-1) { printf("no such vertex"); exit(-1); } G->arcs[n1][n2].adj=1; G->arcs[n2][n1].adj=1; } } int firstAdjVex(MGraph *G,int v)//找到指定节点第一个相邻节点 { for(int i=0;i<G->num_vex;i++) { if(G->arcs[v][i].adj) { return i; } } return -1; } int nextAdjVex(MGraph *G, int v,int w)//找到指定节点下一个相邻节点 { for(int i=w+1;i<G->num_vex;i++) { if(G->arcs[v][i].adj) { return i; }dang } return -1; } void visit(gNode *g) { printf("%d ",g->data); } void BFSTree(MGraph *G,gNode **g) { printf("BFSTree"); gNode *node=NULL; Queue *q=NULL; initQueue(&q); EnQueue(&q,*g); int p=locateVex(G,(*g)->data); visited[p]=true; while(!isEmpty(q)) { bool first =true; gNode* n=DeQueue(&q); node=n; int v=locateVex(G,node->data); for(int i=firstAdjVex(G,v);i>=0;i=nextAdjVex(G,v,i)) { if(!visited[i]) { gNode *gnode=(gNode*)malloc(sizeof(gNode)); gnode->data=G->ver[i]; gnode->lchild=NULL; gnode->nextsibling=NULL; visited[i]=true; EnQueue(&q,gnode); if(first) { node->lchild=gnode; first=false; } else { node->nextsibling=gnode; } node=gnode; } } } } void BFSForest(MGraph *G,gNode **g) { (*g)=NULL; for(int i=0;i<G->num_vex;i++) { visited[i]=false; }dang gNode *node=NULL; int v = locateVex(G,(*g)->data); visited[v]=true; for(int i=0;i<G->num_vex;i++) { if(!visited[i]) { gNode *n=(gNode*)malloc(sizeof(gNode)); n->data=G->ver[i]; n->lchild=NULL; n->nextsibling=NULL; if(!(*g)) { *g=n; } else { node->nextsibling=n;dang } node=n; BFSTree(G,&n); } } } void preOrderTraverse(gNode *g) { visit(g); preOrderTraverse(g->lchild); preOrderTraverse(g->nextsibling); } int main(void) { MGraph G; createGraph(&G); printf("123\n"); gNode *g; printf("456\n"); BFSForest(&G,&g); printf("789\n"); preOrderTraverse(g); return 0; } ```
c语言 实现六度空间理论的源代码
假如给你一个社交网络图,请你对每个节点计算符合六度空间理论的结点总数的百分比。 (1)输入:输入第1行给出两个正整数,分别表示社交网络图的结点数N(1<N<104,表示人数)、边数M(<=33*N,表示社交关系数)。随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个结点的编号(节点从1到N编号)。 (2)输出格式: 对每个结点输出与该节点距离不超过6的结点数占结点总数的百分比,精确到小数点后2位。每个结节点输出一行,格式为“结点编号:(空格)百分比%”
利用C程序编写的语言,求有多少个边集,使得删掉边集里的边后,图里恰好有K个连通块
Problem Description 众所周知,度度熊喜欢图,尤其是联通的图。 今天,它在图上又玩出了新花样,新高度。有一张无重边的无向图, 求有多少个边集,使得删掉边集里的边后,图里恰好有K个连通块。 Input 第一行为T,表示输入数据组数。 对于每组数据,第一行三个整数N,M,K,表示N个点M条边的图。 接下来M行每行两个整数a,b,表示点a和点b之间有一条边。 1≤T≤20 1≤K≤N≤14 0≤M≤N∗(N+1)/2 1≤a,b≤N Output 对第i组数据,输出 Case #i: 然后输出一行,仅包含一个整数,表示方法种数(对 1 000 000 009 取模) 。 Sample Input 3 1 0 1 1 1 1 1 1 3 3 2 1 2 2 3 1 3 Sample Output Case #1: 1 Case #2: 2 Case #3: 3
为什么会出现C语言指针指空的呢
/* * 将node链接到list的末尾 */ static void link_last(ENode *list, ENode *node) { ENode *p=list ; while(p->next_edge) p = p->next_edge; p->next_edge = node; } 编译会提示这方面里的错误 ![图片说明](https://img-ask.csdn.net/upload/201904/28/1556458124_943536.jpg) 0XFEFEFFEFE6表示明指针所指向的空间已经被释放 咋办 求大神解决 完整代码: #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <string.h> #define MAX 100 #define INF (~(0x1<<31)) // 最大值(即0X7FFFFFFF) #define isLetter(a) ((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z'))) #define LENGTH(a) (sizeof(a)/sizeof(a[0])) // 邻接表中表对应的链表的顶点 typedef struct _ENode { int ivex; // 该边的顶点的位置 int weight; // 该边的权 struct _ENode *next_edge; // 指向下一条弧的指针 }ENode, *PENode; // 邻接表中表的顶点 typedef struct _VNode { char data; // 顶点信息 ENode *first_edge; // 指向第一条依附该顶点的弧 }VNode; // 邻接表 typedef struct _LGraph { int vexnum; // 图的顶点的数目 int edgnum; // 图的边的数目 VNode vexs[MAX]; }LGraph; /* * 返回ch在matrix矩阵中的位置 */ static int get_position(LGraph G, char ch) { int i; for(i=0; i<G.vexnum; i++) if(G.vexs[i].data==ch) return i; return -1; } /* * 读取一个输入字符 */ static char read_char() { char ch; do { ch = getchar(); } while(!isLetter(ch)); return ch; } /* * 将node链接到list的末尾 */ static void link_last(ENode *list, ENode *node) { ENode *p=list ; while(p->next_edge) p = p->next_edge; p->next_edge = node; } /* * 创建邻接表对应的图(自己输入) */ LGraph* create_lgraph() { char c1, c2; int v, e; int i, p1, p2; int weight; ENode *node1, *node2; LGraph* pG; // 输入"顶点数"和"边数" printf("输入顶点数: "); scanf("%d", &v); printf("输入边数: "); scanf("%d", &e); if ( v < 1 || e < 1 || (e > (v * (v-1)))) { printf("input error: invalid parameters!\n"); return NULL; } if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL ) return NULL; memset(pG, 0, sizeof(LGraph)); // 初始化"顶点数"和"边数" pG->vexnum = v; pG->edgnum = e; // 初始化"邻接表"的顶点 for(i=0; i<pG->vexnum; i++) { printf("顶点(%d): ", i); pG->vexs[i].data = read_char(); pG->vexs[i].first_edge = NULL; } // 初始化"邻接表"的边 for(i=0; i<pG->edgnum; i++) { // 读取边的起始顶点,结束顶点,权 printf("边(%d): ", i); c1 = read_char(); c2 = read_char(); scanf("%d", &weight); p1 = get_position(*pG, c1); p2 = get_position(*pG, c2); // 初始化node1 node1 = (ENode*)malloc(sizeof(ENode)); node1->ivex = p2; node1->weight = weight; // 将node1链接到"p1所在链表的末尾" if(pG->vexs[p1].first_edge == NULL) pG->vexs[p1].first_edge = node1; else{ link_last(pG->vexs[p1].first_edge, node1); } // 初始化node2 node2 = (ENode*)malloc(sizeof(ENode)); node2->ivex = p1; node2->weight = weight; // 将node2链接到"p2所在链表的末尾" if(pG->vexs[p2].first_edge == NULL) pG->vexs[p2].first_edge = node2; else{ link_last(pG->vexs[p2].first_edge, node2);} free(node1); free(node2); } return pG; } // 边的结构体 typedef struct _edata { char start; // 边的起点 char end; // 边的终点 int weight; // 边的权重 }EData; /* * 打印邻接表图 */ void print_lgraph(LGraph G) { int i; ENode *node; printf("List Graph:\n"); for (i = 0; i < G.vexnum; i++) { printf("%d(%c): ", i, G.vexs[i].data); node = G.vexs[i].first_edge; while (node != NULL) { printf("%d(%c) ", node->ivex, G.vexs[node->ivex].data); node = node->next_edge; } printf("\n"); } } /* * 获取G中边<start, end>的权值;若start和end不是连通的,则返回无穷大。 */ int getWeight(LGraph G, int start, int end) { ENode *node; if (start==end) return 0; node = G.vexs[start].first_edge; while (node!=NULL) { if (end==node->ivex) return node->weight; node = node->next_edge; } return INF; } /* * 获取图中的边 */ EData* get_edges(LGraph G) { int i; int index=0; ENode *node; EData *edges; edges = (EData*)malloc(G.edgnum*sizeof(EData)); for (i=0; i<G.vexnum; i++) { node = G.vexs[i].first_edge; while (node != NULL) { if (node->ivex > i) { edges[index].start = G.vexs[i].data; // 起点 edges[index].end = G.vexs[node->ivex].data; // 终点 edges[index].weight = node->weight; // 权 index++; } node = node->next_edge; } } return edges; } /* * 对边按照权值大小进行排序(由小到大) */ void sorted_edges(EData* edges, int elen) { int i,j; for (i=0; i<elen; i++) { for (j=i+1; j<elen; j++) { if (edges[i].weight > edges[j].weight) { // 交换"第i条边"和"第j条边" EData tmp = edges[i]; edges[i] = edges[j]; edges[j] = tmp; } } } } /* * 获取i的终点 */ int get_end(int vends[], int i) { while (vends[i] != 0) i = vends[i]; return i; } /* * 克鲁斯卡尔(Kruskal)最小生成树 */ void kruskal(LGraph G) { int i,m,n,p1,p2; int length; int index = 0; // rets数组的索引 int vends[MAX]={0}; // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。 EData rets[MAX]; // 结果数组,保存kruskal最小生成树的边 EData *edges; // 图对应的所有边 // 获取"图中所有的边" edges = get_edges(G); // 将边按照"权"的大小进行排序(从小到大) sorted_edges(edges, G.edgnum); for (i=0; i<G.edgnum; i++) { p1 = get_position(G, edges[i].start); // 获取第i条边的"起点"的序号 p2 = get_position(G, edges[i].end); // 获取第i条边的"终点"的序号 m = get_end(vends, p1); // 获取p1在"已有的最小生成树"中的终点 n = get_end(vends, p2); // 获取p2在"已有的最小生成树"中的终点 // 如果m!=n,意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路 if (m != n) { vends[m] = n; // 设置m在"已有的最小生成树"中的终点为n rets[index++] = edges[i]; // 保存结果 } } free(edges); // 统计并打印"kruskal最小生成树"的信息 length = 0; for (i = 0; i < index; i++) length += rets[i].weight; printf("Kruskal=%d: ", length); for (i = 0; i < index; i++) printf("(%c,%c) ", rets[i].start, rets[i].end); printf("\n"); } void main() { LGraph* pG; pG = create_lgraph(); print_lgraph(*pG); // 打印图 kruskal(*pG); // kruskal算法生成最小生成树 }
是否存在欧拉回路用C语言的判断
Problem Description 欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路? Input 测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是节点数N ( 1 < N < 1000 )和边数M;随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个节点的编号(节点从1到N编号)。当N为0时输入结 束。 Output 每个测试用例的输出占一行,若欧拉回路存在则输出1,否则输出0。 Sample Input 3 3 1 2 1 3 2 3 3 2 1 2 2 3 0 Sample Output 1 0
对于下面的有向图,请给出该图的(1) 强连通分量,(2) 每个顶点的入度和出度。
对于下面的有向图,请给出该图的(1) 强连通分量,(2) 每个顶点的入度和出度。 ![图片说明](https://img-ask.csdn.net/upload/201904/10/1554855872_926997.png) 第1小题,涉及“连通分量”概念,特别注意是一个图的每个连通量是不相交的子图
《MySQL 性能优化》之理解 MySQL 体系结构
本文介绍 MySQL 的体系结构,包括物理结构、逻辑结构以及插件式存储引擎。
程序员请照顾好自己,周末病魔差点一套带走我。
程序员在一个周末的时间,得了重病,差点当场去世,还好及时挽救回来了。
卸载 x 雷某度!GitHub 标星 1.5w+,从此我只用这款全能高速下载工具!
作者 | Rocky0429 来源 | Python空间 大家好,我是 Rocky0429,一个喜欢在网上收集各种资源的蒟蒻… 网上资源眼花缭乱,下载的方式也同样千奇百怪,比如 BT 下载,磁力链接,网盘资源等等等等,下个资源可真不容易,不一样的方式要用不同的下载软件,因此某比较有名的 x 雷和某度网盘成了我经常使用的工具。 作为一个没有钱的穷鬼,某度网盘几十 kb 的下载速度让我...
讲真,这两个IDE插件,可以让你写出质量杠杠的代码
周末躺在床上看《拯救大兵瑞恩》 周末在闲逛的时候,发现了两个优秀的 IDE 插件,据说可以提高代码的质量,我就安装了一下,试了试以后发现,确实很不错,就推荐给大家。 01、Alibaba Java 代码规范插件 《阿里巴巴 Java 开发手册》,相信大家都不会感到陌生,其 IDEA 插件的下载次数据说达到了 80 万次,我今天又贡献了一次。嘿嘿。 该项目的插件地址: https://github....
为什么猝死的都是程序员,基本上不见产品经理猝死呢?
相信大家时不时听到程序员猝死的消息,但是基本上听不到产品经理猝死的消息,这是为什么呢? 我们先百度搜一下:程序员猝死,出现将近700多万条搜索结果: 搜索一下:产品经理猝死,只有400万条的搜索结果,从搜索结果数量上来看,程序员猝死的搜索结果就比产品经理猝死的搜索结果高了一倍,而且从下图可以看到,首页里面的五条搜索结果,其实只有两条才是符合条件。 所以程序员猝死的概率真的比产品经理大,并不是错...
害怕面试被问HashMap?这一篇就搞定了!
声明:本文以jdk1.8为主! 搞定HashMap 作为一个Java从业者,面试的时候肯定会被问到过HashMap,因为对于HashMap来说,可以说是Java集合中的精髓了,如果你觉得自己对它掌握的还不够好,我想今天这篇文章会非常适合你,至少,看了今天这篇文章,以后不怕面试被问HashMap了 其实在我学习HashMap的过程中,我个人觉得HashMap还是挺复杂的,如果真的想把它搞得明明白...
毕业5年,我问遍了身边的大佬,总结了他们的学习方法
我问了身边10个大佬,总结了他们的学习方法,原来成功都是有迹可循的。
python爬取百部电影数据,我分析出了一个残酷的真相
2019年就这么匆匆过去了,就在前几天国家电影局发布了2019年中国电影市场数据,数据显示去年总票房为642.66亿元,同比增长5.4%;国产电影总票房411.75亿元,同比增长8.65%,市场占比 64.07%;城市院线观影人次17.27亿,同比增长0.64%。 看上去似乎是一片大好对不对?不过作为一名严谨求实的数据分析师,我从官方数据中看出了一点端倪:国产票房增幅都已经高达8.65%了,为什...
推荐10个堪称神器的学习网站
每天都会收到很多读者的私信,问我:“二哥,有什么推荐的学习网站吗?最近很浮躁,手头的一些网站都看烦了,想看看二哥这里有什么新鲜货。” 今天一早做了个恶梦,梦到被老板辞退了。虽然说在我们公司,只有我辞退老板的份,没有老板辞退我这一说,但是还是被吓得 4 点多都起来了。(主要是因为我掌握着公司所有的核心源码,哈哈哈) 既然 4 点多起来,就得好好利用起来。于是我就挑选了 10 个堪称神器的学习网站,推...
这些软件太强了,Windows必装!尤其程序员!
Windows可谓是大多数人的生产力工具,集娱乐办公于一体,虽然在程序员这个群体中都说苹果是信仰,但是大部分不都是从Windows过来的,而且现在依然有很多的程序员用Windows。 所以,今天我就把我私藏的Windows必装的软件分享给大家,如果有一个你没有用过甚至没有听过,那你就赚了????,这可都是提升你幸福感的高效率生产力工具哦! 走起!???? NO、1 ScreenToGif 屏幕,摄像头和白板...
阿里面试,面试官没想到一个ArrayList,我都能跟他扯半小时
我是真的没想到,面试官会这样问我ArrayList。
曾经优秀的人,怎么就突然不优秀了。
职场上有很多辛酸事,很多合伙人出局的故事,很多技术骨干被裁员的故事。说来模板都类似,曾经是名校毕业,曾经是优秀员工,曾经被领导表扬,曾经业绩突出,然而突然有一天,因为种种原因,被裁员了,...
C语言荣获2019年度最佳编程语言
关注、星标公众号,不错过精彩内容作者:黄工公众号:strongerHuang近日,TIOBE官方发布了2020年1月编程语言排行榜单。我在前面给过一篇文章《2019年11月C语言接近Ja...
大学四年因为知道了这32个网站,我成了别人眼中的大神!
依稀记得,毕业那天,我们导员发给我毕业证的时候对我说“你可是咱们系的风云人物啊”,哎呀,别提当时多开心啦????,嗯,我们导员是所有导员中最帅的一个,真的???? 不过,导员说的是实话,很多人都叫我大神的,为啥,因为我知道这32个网站啊,你说强不强????,这次是绝对的干货,看好啦,走起来! PS:每个网站都是学计算机混互联网必须知道的,真的牛杯,我就不过多介绍了,大家自行探索,觉得没用的,尽管留言吐槽吧???? 社...
良心推荐,我珍藏的一些Chrome插件
上次搬家的时候,发了一个朋友圈,附带的照片中不小心暴露了自己的 Chrome 浏览器插件之多,于是就有小伙伴评论说分享一下我觉得还不错的浏览器插件。 我下面就把我日常工作和学习中经常用到的一些 Chrome 浏览器插件分享给大家,随便一个都能提高你的“生活品质”和工作效率。 Markdown Here Markdown Here 可以让你更愉快的写邮件,由于支持 Markdown 直接转电子邮...
看完这篇HTTP,跟面试官扯皮就没问题了
我是一名程序员,我的主要编程语言是 Java,我更是一名 Web 开发人员,所以我必须要了解 HTTP,所以本篇文章就来带你从 HTTP 入门到进阶,看完让你有一种恍然大悟、醍醐灌顶的感觉。 最初在有网络之前,我们的电脑都是单机的,单机系统是孤立的,我还记得 05 年前那会儿家里有个电脑,想打电脑游戏还得两个人在一个电脑上玩儿,及其不方便。我就想为什么家里人不让上网,我的同学 xxx 家里有网,每...
应届生/社招面试最爱问的几道Java基础问题
本文已经收录自笔者开源的 JavaGuide: https://github.com/Snailclimb (【Java学习 面试指南】 一份涵盖大部分Java程序员所需要掌握的核心知识)如果觉得不错的还,不妨去点个Star,鼓励一下! 一 为什么 Java 中只有值传递? 首先回顾一下在程序设计语言中有关将参数传递给方法(或函数)的一些专业术语。按值调用(call by value)表...
史上最全的IDEA快捷键总结
现在Idea成了主流开发工具,这篇博客对其使用的快捷键做了总结,希望对大家的开发工作有所帮助。
阿里程序员写了一个新手都写不出的低级bug,被骂惨了。
这种新手都不会范的错,居然被一个工作好几年的小伙子写出来,差点被当场开除了。
谁是华为扫地僧?
是的,华为也有扫地僧!2020年2月11-12日,“养在深闺人不知”的华为2012实验室扫地僧们,将在华为开发者大会2020(Cloud)上,和大家见面。到时,你可以和扫地僧们,吃一个洋...
Idea 中最常用的10款插件(提高开发效率),一定要学会使用!
学习使用一些插件,可以提高开发效率。对于我们开发人员很有帮助。这篇博客介绍了开发中使用的插件。
AI 没让人类失业,搞 AI 的人先失业了
最近和几个 AI 领域的大佬闲聊 根据他们讲的消息和段子 改编出下面这个故事 如有雷同 都是巧合 1. 老王创业失败,被限制高消费 “这里写我跑路的消息实在太夸张了。” 王葱葱哼笑一下,把消息分享给群里。 阿杰也看了消息,笑了笑。在座几位也都笑了。 王葱葱是个有名的人物,21岁那年以全额奖学金进入 KMU 攻读人工智能博士,累计发表论文 40 余篇,个人技术博客更是成为深度学习领域内风向标。 ...
2020年,冯唐49岁:我给20、30岁IT职场年轻人的建议
点击“技术领导力”关注∆每天早上8:30推送 作者|Mr.K 编辑| Emma 来源|技术领导力(ID:jishulingdaoli) 前天的推文《冯唐:职场人35岁以后,方法论比经验重要》,收到了不少读者的反馈,觉得挺受启发。其实,冯唐写了不少关于职场方面的文章,都挺不错的。可惜大家只记住了“春风十里不如你”、“如何避免成为油腻腻的中年人”等不那么正经的文章。 本文整理了冯...
最全最强!世界大学计算机专业排名总结!
我正在参与CSDN200进20,希望得到您的支持,扫码续投票5次。感谢您! (为表示感谢,您投票后私信我,我把我总结的人工智能手推笔记和思维导图发送给您,感谢!) 目录 泰晤士高等教育世界大学排名 QS 世界大学排名 US News 世界大学排名 世界大学学术排名(Academic Ranking of World Universities) 泰晤士高等教育世界大学排名 中国共...
一份王者荣耀的英雄数据报告
咪哥杂谈本篇阅读时间约为 6 分钟。1前言前一阵写了关于王者的一些系列文章,从数据的获取到数据清洗,数据落地,都是为了本篇的铺垫。今天来实现一下,看看不同维度得到的结论。2环境准备本次实...
作为一名大学生,如何在B站上快乐的学习?
B站是个宝,谁用谁知道???? 作为一名大学生,你必须掌握的一项能力就是自学能力,很多看起来很牛X的人,你可以了解下,人家私底下一定是花大量的时间自学的,你可能会说,我也想学习啊,可是嘞,该学习啥嘞,不怕告诉你,互联网时代,最不缺的就是学习资源,最宝贵的是啥? 你可能会说是时间,不,不是时间,而是你的注意力,懂了吧! 那么,你说学习资源多,我咋不知道,那今天我就告诉你一个你必须知道的学习的地方,人称...
那些年,我们信了课本里的那些鬼话
教材永远都是有错误的,从小学到大学,我们不断的学习了很多错误知识。 斑羚飞渡 在我们学习的很多小学课文里,有很多是错误文章,或者说是假课文。像《斑羚飞渡》: 随着镰刀头羊的那声吼叫,整个斑羚群迅速分成两拨,老年斑羚为一拨,年轻斑羚为一拨。 就在这时,我看见,从那拨老斑羚里走出一只公斑羚来。公斑羚朝那拨年轻斑羚示意性地咩了一声,一只半大的斑羚应声走了出来。一老一少走到伤心崖,后退了几步,突...
一个程序在计算机中是如何运行的?超级干货!!!
强烈声明:本文很干,请自备茶水!???? 开门见山,咱不说废话! 你有没有想过,你写的程序,是如何在计算机中运行的吗?比如我们搞Java的,肯定写过这段代码 public class HelloWorld { public static void main(String[] args) { System.out.println("Hello World!"); } ...
【蘑菇街技术部年会】程序员与女神共舞,鼻血再次没止住。(文末内推)
蘑菇街技术部的年会,别开生面,一样全是美女。
那个在阿里养猪的工程师,5年了……
简介: 在阿里,走过1825天,没有趴下,依旧斗志满满,被称为“五年陈”。他们会被授予一枚戒指,过程就叫做“授戒仪式”。今天,咱们听听阿里的那些“五年陈”们的故事。 下一个五年,猪圈见! 我就是那个在养猪场里敲代码的工程师,一年多前我和20位工程师去了四川的猪场,出发前总架构师慷慨激昂的说:同学们,中国的养猪产业将因为我们而改变。但到了猪场,发现根本不是那么回事:要个WIFI,没有;...
立即提问

相似问题

0
数据结构的图论方面的问题,求这个图上的边的个数的和,要运用C语言技术
0
一个数据结构有关连通图生成算法的一个问题,用C语言怎么解决这个问题?
0
二维字符连通图的问题,运用C语言的知识的综合理解的实现
0
连通图的环的判断问题数据结构的设计,怎么利用C语言的编写形式?
0
连通图数据结构上面的一个路径的搜索的算法问题,采用C语言的程序的设计的办法
1
对于下面的有向图,请给出该图的(1) 强连通分量,(2) 每个顶点的入度和出度。
0
连通图上的点的可达性的判断的算法问题,怎么利用C语言的程序的设计的方式来实现的?
0
连通图上的距离的搜索的问题,怎么利用C语言的程序的设计的方式实现的呢
0
连通图的稳定状态的计算用的数据结构,怎么采用C程序语言的编程算法的实现的过程
0
连通图的数据结构上的一个算法的视线,怎么能采用C语言的程序的设计的思想去实现?
0
为什么会出现C语言指针指空的呢
0
利用C程序编写的语言,求有多少个边集,使得删掉边集里的边后,图里恰好有K个连通块
0
8个节点的连通图矩阵怎么用C语言的程序的编写设计的过程方式有效实现的思维是什么
1
欧拉回路避桥法的扩展:遍历无向图里的所有边,当这个图不是欧拉回路时,怎样使得走过的重复边最少?
0
连通的图的计算表达问题,要求使用C语言来实现
0
是否存在欧拉回路用C语言的判断
1
CCF 317号子任务 运行错误 0分