PTA 7-2 邻接表创建无向图 (20分)

ゝ一纸荒年。 2023-03-14 05:58 2阅读 0赞

# PTA 7-2 邻接表创建无向图 (20分) #

采用邻接表创建无向图G ，依次输出各顶点的度。

## 输入格式: ##

输入第一行中给出2个整数i(0<i≤10)，j(j≥0)，分别为图G的顶点数和边数。 输入第二行为顶点的信息，每个顶点只能用一个字符表示。 依次输入j行，每行输入一条边依附的顶点。

## 输出格式: ##

依次输出各顶点的度，行末没有最后的空格。

## 输入样例: ##

5 7
    ABCDE
    AB
    AD
    BC
    BE
    CD
    CE
    DE

## 输出样例: ##

2 3 3 3 3

## **一道水题，无需建图也能AC，第一种方法无需建图，第二种方法建图** ##

## 【程序实现】 ##

## 无需建图 ##

#include<bits/stdc++.h>
    using namespace std;
    int main(){
        
    	map<char, int> m;
    	int i, j;
    	char G[15], a, b;
    	scanf("%d %d",&i,&j);
    	getchar();
    	scanf("%s",G);
    	getchar();
    	while(j--) {
        
    		scanf("%c%c",&a,&b);
    		getchar();
    		m[a]++;
    		m[b]++;
    	}
    	cout<<m[G[0]];
    	for(int k = 1; k < i; k++)
    		cout<<' '<<m[G[k]];
    	return 0;
    }

## 建图 ##

#include<bits/stdc++.h>
    using namespace std;
    struct Graph {
        
    	char data;
    	struct Graph *next;
    };
    int i, j;
    int search(struct Graph p) {
        
    	struct Graph *head = &p;
    	int c = 0;
    	while (head->next) {
        
    		c++;
    		head = head->next;
    	}
    	return c;
    }
    int main(){
        
    	map<char, int> m;
    	char  a, b;
    	struct Graph ls[15];
    	scanf("%d %d",&i,&j);
    	getchar();
    	for(int k = 0; k <i; k++) {
        
    		cin>>a;
    		m[a] = k;
    		ls[k].next = NULL;
    	}
    	getchar();
    	while(j--) {
        
    		scanf("%c%c",&a,&b);
    		getchar();
    		struct Graph *t = new struct Graph;
    		t->data = b;
    		t->next = ls[m[a]].next;
    		ls[m[a]].next = t;
    		t = new struct Graph;
    		t->data = a;
    		t->next = ls[m[b]].next;
    		ls[m[b]].next = t;
    	}
    	cout<<search(ls[0]);
    	for(int k = 1; k < i; k++)
    		cout<<' '<<search(ls[k]);
    	return 0;
    }