图的前向星表示

图的前向星表示1

时间限制:1秒        内存限制:128M

题目描述

给定一个有向图的信息,按照前插法的方式输出每个节点的邻接点。

输入描述

第一行,两个整数n,m(1 <= n,m <= 10^5),n表示图的节点的个数,m表示图中的边数。

接下来m行,每行两个整数x,y,表示x能够直接到达y。

输出描述

输出共占n行,第i行开头为i节点和一个冒号“:”,之后为i的所有邻接点编号,每个编号中间用空格隔开,如果i没有邻接点,则输出zero。

样例

输入

2
3
1 8 2
4
10 7 6 14

输出

8
24

提示

对于第一组样例,阿福选择第2家店铺行窃,获得的现金数量为8。 

对于第二组样例,阿福选择第1和4家店铺行窃,获得的现金数量为10+14=24。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXNM=100005;
int first[MAXNM],tot=-1;
struct node{
	int ver;
	int nxt;
}a[MAXNM];
void add(int u,int v){
	a[++tot].ver=v;
	a[tot].nxt=first[u];
	first[u]=tot;
}
int main(){
	memset(first,-1,sizeof(first));
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		add(x,y);
	}
	for(int i=1;i<=n;i++){
		printf("%d: ",i);
		if(first[i]==EOF){
			printf("zero\n");
			continue;
		}
		for(int j=first[i];j!=-1;j=a[j].nxt){
			printf("%d ",a[j].ver);
		}
		printf("\n");
	}
	return 0;
}

图的前向星表示2

时间限制:1秒        内存限制:128M

题目描述

给定一个无向图的信息,按照前插法的方式输出每个节点的邻接点

输入描述

第一行,两个整数n,m(1 <= n,m <= 10^5),n表示图的节点的个数,m表示图中的边数。

接下来m行,每行两个整数x,y。表示x和y之间有一条无向边。

输出描述

输出共占n行,第i行开头为i节点和一个冒号“:”,之后为i的所有邻接点编号,每个编号中间用空格隔开,如果i没有邻接点,则输出zero。

样例

输入

5 4
1 2
1 3
1 4
2 5

输出

1: 4 3 2
2: 5 1
3: 1
4: 1
5: 2
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXNM=100005;
int first[MAXNM],tot=-1;
struct node{
	int ver;
	int nxt;
}a[MAXNM];
void add(int u,int v){
	a[++tot].ver=v;
	a[tot].nxt=first[u];
	first[u]=tot;
}
int main(){
	memset(first,-1,sizeof(first));
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++){
		printf("%d: ",i);
		if(first[i]==EOF){
			printf("zero\n");
			continue;
		}
		for(int j=first[i];j!=-1;j=a[j].nxt){
			printf("%d ",a[j].ver);
		}
		printf("\n");
	}
	return 0;
}

图的前向星表示3

时间限制:1秒        内存限制:128M

题目描述

给定一个有向图的信息,按照字典序的方式输出每个节点的邻接点

输入描述

第一行,两个整数n,m(1 <= n,m <= 10^5),n表示图的节点的个数,m表示图中的边数。

接下来m行,每行两个整数x,y,表示x能够直接到达y。

输出描述

输出共占n行,第i行开头为i节点和一个冒号“:”,之后为i的所有邻接点编号,每个编号中间用空格隔开,如果i没有邻接点,则输出zero。

 样例

输入

5 4
1 2
1 3
1 4
2 5

输出

1: 2 3 4
2: 5
3: zero
4: zero
5: zero
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXNM=100005;
int first[MAXNM],tot=-1;
struct node{
	int ver;
	int nxt;
}a[MAXNM];
void add(int u,int v){
	a[++tot].ver=v;
	a[tot].nxt=first[u];
	first[u]=tot;
}
int main(){
	memset(first,-1,sizeof(first));
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		add(x,y);
	}
	for(int i=1;i<=n;i++){
		printf("%d: ",i);
		if(first[i]==EOF){
			printf("zero\n");
			continue;
		}
		int xx[MAXNM],cnt=1;
		for(int j=first[i];j!=-1;j=a[j].nxt){
			xx[cnt++]=a[j].ver;
		}
		sort(xx+1,xx+cnt);
		for(int i=1;i<cnt;i++){
			printf("%d ",xx[i]);
		}
		printf("\n");
	}
	return 0;
}

 

图的前向星表示4

时间限制:1秒        内存限制:128M

题目描述

给定一个有向图的信息,按照前插法的形式输出每个节点的邻接点。

输入描述

第一行,两个整数n,m(1 <= n,m <= 10^5),n表示图的节点的个数,m表示图中的边数。

接下来m行,每行三个整数x,y,z。表示x能够直接到达y,并且权值为z。

输出描述

输出共占n行,第i行开头为i节点和一个冒号“:”,之后为i的所有邻接点的编号和这条边的权值,用"()"括起来,如果i没有邻接点,则输出zero。

样例

输入

5 5
1 2 2
1 3 6
1 4 7
2 3 8
2 4 9

输出

1: (4,7) (3,6) (2,2)
2: (4,9) (3,8)
3: zero
4: zero
5: zero
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXNM=100005;
int first[MAXNM],tot=-1;
struct node{
	int ver;
	int nxt;
	int wei;
}a[MAXNM];
void add(int u,int v,int w){
	a[++tot].ver=v;
	a[tot].wei=w;
	a[tot].nxt=first[u];
	first[u]=tot;
}
int main(){
	memset(first,-1,sizeof(first));
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		add(x,y,z);
	}
	for(int i=1;i<=n;i++){
		printf("%d: ",i);
		if(first[i]==EOF){
			printf("zero\n");
			continue;
		}
		for(int j=first[i];j!=-1;j=a[j].nxt){
			printf("(%d,%d) ",a[j].ver,a[j].wei);
		}
		printf("\n");
	}
	return 0;
}

 

上一篇:x的平方根


下一篇:【SPOJ】32952 ADAFTBLL(树上带修莫队)