题目描述
给定一个无向图，n个顶点m条边。进行q次询问，每次询问一个顶点的邻接点的数量。
顶点编号为1，2，...，n。
输入
第一行：两个整数n m，空格分开，n表示顶点数，m表示边数(1<=n<=100, 1<=m<=1000)
以下m行，每行两个整数f，t，表明从顶点f到顶点t有一条边
第m+2行：一个整数q，表示询问次数
以下q行，每行一个整数v，表示要询问顶点v的邻接点
输出
q行，每行为要询问的顶点的邻接点数量。
样例输入输出
输入：
4 5
1 2
1 3
1 4
2 3
3 4
2
1
2
输出：
3
2
方法一：邻接矩阵
邻接矩阵就声明一个二维数组来保存是否有连接边，由于是无向图所以若存在边(i, j) 则edge[i][j] = 1且edge[j][i] = 1，否则为0
邻接矩阵是最好写的，话不多说开始分析~
STEP 1:输入n,m,输入m组f,t,在邻接矩阵中设置下标为f,t和t,f为1
STEP 2:输入q及q个询问，每次邻接点归零，输入V，n次循环，edge[v][z](z是循环次数)是1就说明是临接点，sum++
#include<bits/stdc++.h>
using namespace std;
int n,m,q,v,sum,edge[105][105];
int main()
{cin>>n>>m;for(int i=1;i<=m;i++){int f,t;cin>>f>>t;edge[f][t]=edge[t][f]=1;}cin>>q;while(q--){cin>>v;sum=0;for(int z=1;z<=n;z++){if(edge[v][z]){sum++;}}cout<<sum<<'\n';}
}
方法2:链式前向星
这个比较难，咱会将的稍微详细一点~
先举个栗子
如果有下图
辣么他的邻接表就可以是下图
链式前向星是邻接表的一种，类似于链式存储结构，所以我们可以声明结点池
struct Edge
{int to;//通过这条边到达的顶点编号int next;//边链表下一个结点的地址
}edge[M];//结点池 最多有M条边
int p;//结点池指针
int head[N];//头结点数组 最多N个顶点链式前向星必须插入，而且只能使用头插(尾插你取不到地址的)
先申请新节点，先把to值设成v(具体参照代码)，再把下一个结点的地址设成第u个头结点，最后第u个头结点地址变为np,完成
void addEdge(int u, int v)
{int np = ++p;edge[np].to = v;edge[np].next = head[u];head[u] = np;
}在主函数中插入就跟邻接矩阵差不多了，请参见完整代码第21~22行
总体思路：
STEP 1:声明结点池
STEP 2:声明插入函数(这两步参照上面解析)
STEP 3:输入，每次调用两次头插
STEP 4:输入q及q个询问，每次邻接点z归零，输入u，遍历头节点数组，每次z++，完成遍历后输出
#include<bits/stdc++.h>
using namespace std;
struct Edge
{int to,next;
}edge[1005];
int p,head[105],n,m,f,t,q,u,z;
void addEdge(int u,int v)
{int np=++p;edge[np].to=v;edge[np].next=head[u];head[u]=np;
}
int main()
{cin>>n>>m;for(int i=1;i<=m;i++){cin>>f>>t;addEdge(f,t);addEdge(t,f);}cin>>q;while(q--){z=0;cin>>u;for(int i=head[u];i!=0;i=edge[i].next){z++;}cout<<z<<'\n';}
}
方法3:vector邻接表
这个也好理解，咱就直接说步骤哩~
其实身为天字第x号大懒人，就直接在链式前向星基础上修改就行
STEP 1:输入n,m,输入m组f,t,在vector邻接表中分别插入：第f个插入t，第t个插入f
STEP 2:输入q及q个询问，输入u，输出第u个邻接表的长度就行
#include<bits/stdc++.h>
using namespace std;
int n,m,f,t,q,u;
vector<int>edge[105];
int main()
{cin>>n>>m;for(int i=1;i<=m;i++){cin>>f>>t;edge[f].push_back(t);edge[t].push_back(f);}cin>>q;while(q--){cin>>u;cout<<edge[u].size()<<'\n';}
} 
