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;
}