# 考研数据结构关于图的操作

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000;

//定义边表节点结构
typedef struct ArcNode{
struct ArcNode * next;  //指向顶点的下一个邻接点
}ArcNode;

//定义顶点表节点结构
typedef struct VNode{
int data;
ArcNode *first; //边表头节点，指向顶点的第一个邻接点
}VNode;

typedef struct AGraph{
VNode VList[maxn];
int n;
int e;
}AGraph;

int findnode(AGraph *g, int c){
for(int i = 0; i < g->n; i ++){
if(g->VList[i].data == c)  {  return i;}
}
return -1;
}

void createAgraph(int n, int m){
int l = 0, k = 0, x = 0, y = 0;
AGraph *g = (AGraph *)malloc(sizeof(AGraph));
g -> n = n;
g -> e = m;
for(int i = 0; i < n; i ++){
scanf("%d", &(g -> VList[i].data));
g -> VList[i].first = NULL;
}

for(int j = 0; j < m; j ++){
scanf("%d%d", &x, &y);
l = findnode(g, x);
k = findnode(g, y);
ArcNode *arcl = (ArcNode *)malloc(sizeof(ArcNode));
arcl -> next = g -> VList[l].first;
g -> VList[l].first = arcl;

ArcNode *arck = (ArcNode *)malloc(sizeof(ArcNode));
arck -> next = g -> VList[k].first;
g -> VList[k].first = arck;
}

//输出每个节点的度
for(int i = 0; i < g->n; i ++){
int s = 0;
for(ArcNode *p = g->VList[i].first;  p != NULL; p = p->next) s ++;
if(i == 0)  cout << s;
else  cout << " " << s;
}

}

int main(){
int n, m;
scanf("%d%d", &n, &m);
createAgraph(n, m);
return 0;
}



#include <bits/stdc++.h>
using namespace std;

const int maxn = 100;

//定义边表节点结构
typedef struct ArcNode{
struct ArcNode * next;  //指向顶点的下一个邻接点
}ArcNode;

//定义顶点表节点结构
typedef struct VNode{
int data;
ArcNode *first; //边表头节点，指向顶点的第一个邻接点
}VNode;

typedef struct AGraph{
VNode VList[maxn];
int n;
int e;
}AGraph;

typedef struct MGraph{
int edges[maxn][maxn];
int n;
int e;
}MGraph;

void MGraphToAGraph(MGraph M){
ArcNode *arc;
AGraph *g = (AGraph *)malloc(sizeof(AGraph));
g->n = M.n;
g->e = M.e;
for(int i = 0; i < g->n ; i ++){
g->VList[i].first = NULL;
}

for(int i = 0; i < g->n; i ++){
for(int j = 0; j < g->e; j ++){
if(M.edges[i][j]){
arc = (ArcNode *)malloc(sizeof(ArcNode));
arc -> next = g->VList[i].first;
g->VList[i].first = arc;
}
}
}
}

int main(){
int n, m;
MGraph M;
scanf("%d%d", &n, &m);
M.n = n;
M.e = m;
for(int i = 0; i < n; i ++){
for(int j = 0; j < m; j ++){
scanf("%d", &M.edges[i][j]);
}
}
MGraphToAGraph(M);
return 0;
}


void indgeree(AGraph g){
ArcNode *p;
int cnt;
for(int k = 0; k < g->n; k ++){
cnt = 0;
for(int j = 0; j < g-> n; j ++){
p = g -> VList[j].first;
while(p != NULL){
cnt ++;
break;
}
p = p -> next;
}
}
cout << "顶点" << k << "的入度为:" << cnt << endl;
}
}


void outdegree(AGraph g){
ArcNode *p;
int cnt;
for(int i = 0; i < g.n; i ++){
cnt = 0;
p = g.VList[i].first;
while(p != NULL){
cnt ++;
p = p -> next;
}
cout << "顶点" << i << "的出度为:" << cnt << endl;
}
}


bool vis[maxn];
int num = 0;

void dfs(AGraph g, int i){
ArcNOde *p;
vis[i] = true;
num ++;
p = g -> VList[i].first;
while(p != NULL){
dfs(g, p -> next);
}
p = p -> next;
}
}

int getnum(Agraph g, int k){
int i, cnt = 0;
for(int i = 0; i < g -> n; i ++){
vis[i] = 0;
}
for(int i = 0; i < g -> n; i ++){
if(!vis[i]){
dfs(g, i);
if(num == k){
cnt ++;
}
}
}
return cnt;
}


void d_edge(AGraph *g, int i, int j){
ArcNOde p = g -> VList[i].first;
ArcNode pre = NULL;
while(p != NULL){
if(pre == NULL){
g -> VList[i].first = p -> next;
}
else{
pre -> next = p -> next;
}
free(p);
}
else{
pre = p;
p = p -> next;
}
}

p = g -> vlist[j].first;
pre = NULL;
while(p != NULL){
if(pre == NULL){
g[j] -> vlist[i].first = p -> next;
}
else{
pre -> next = p -> next;
free(p);
}
}
else{
pre = p;
p = p -> next;
}
}
}


void invert(AGraph *gin, AGraph *gout){
gin -> n = gout -> n;
gin -> e = gout -> e;

for(int i = 0; i < gout -> n; i ++){
gin -> VList[i].data = gout -> VList[i].data;
gin -> VList[i].first = null;
}

for(int i = 0; i < gout -> n; i ++){
ArcNode *p, *s;
p = gout -> VList[i].first;//取出邻接表中第i个顶点的指向邻接表的指针

while(p != NULL){//遍历邻接表中第i个顶点所有邻接边
int j = p -> adjv;
s = new ArcNode;
s -> adjv = i;//将 i 挂到 g->VList[j]上
s -> next = gin -> VList[j].first;//将 i 挂到 j上
gin -> vlist[j].first = s;
p = p -> next;
}
}


int vis[maxn], path[maxn];
void dfs(AGraph *g, int vi, int vj, int d){
vis[vi] = 1;
path[d ++] = vi;
if(vi == vj && d == k){
for(int i = 0; i < d; i ++){
cout << path[i] << " " ;
}
cout << endl;
}
ArcNode *p = g -> vlist[vi].first;
int v;
while(p != NULL){
if(vis[v] == 0){
dfs(g, v, vj, d);
}
p = p -> next;
}
vis[vi] = 0;
d --;
}


bool istree(AGraph *g){
int vis[maxn];
for(int i = 0; i < g -> n; i ++){
vis[i] = 0;
}
int Vnum = 0, Enum = 0;
dfs(g, 1, Vnum, Enum, vis);
if(Vnum == g -> n && Enum == 2 * (g -> n - 1))//边数为2∗(n−1)
return true;
else
return false;
}

void dfs(Agraph *g, int v, int *Vnum, int *Enum, int vis[]){
vis[v] = 1;
Vnum ++;
ArcNOde *p = g -> vlist[v].firs;
while(p != NULL){
Enum ++;
p = p -> next;
}
}


void bfs_trace(Graph *g){
int i, cnt = 0;
int vis[maxn];
for(int i = 0; i < g -> n; i ++){
vis[i] = 0;
}
for(int i = 0; i < g -> n; i ++){
if(!vis[i]){
cnt ++;
dfs(g, i);
}
}
}

void dfs(Graph *g, int i){
ArcNode *p;
vis[i] = 1;
p = vlis[i].first;
while(p != NULL){