1 条题解

  • 0
    @ 2025-10-10 19:47:19

    C++ :

    #include <bits/stdc++.h>
    using namespace std;
    
    const int MAXN = 1e5;
    //采用链式前向星的方式来存储图(边)
    struct Edge{
    	//从u出发,到v去,next表示从u出发的
    	//上一条边在edge数组的哪个位置 
    	int u,v,next;
    }edge[MAXN * 2];
    
    //存储每个点的最后一条边的起始位置
    int pre[1000100];
    int k = 1;//数组下标
    int n;//总共有多少条边 
    
    //追加点 
    void add(int from,int to){
    	edge[k].u = from;
    	edge[k].v = to;
    	edge[k].next = pre[from];//前一条边的下标,形成边的链表
    	pre[from] = k;//更新u的上一条边的序号
    	k++; 
    } 
    
    //遍历函数 
    //遍历函数 
    void print(){
    	//遍历n个起点
    	for(int i = 1;i <= n;i++){
    		if(pre[i] != 0) cout<<i<<endl;
    		//遍历以i为起点的边 
    		for(int j = pre[i];j != 0;j = edge[j].next){
    			cout<<edge[j].v;
    			if(edge[j].next != 0) cout<<" ";
    		}
    		if(pre[i] != 0) cout<<endl;
    	} 
    	
    }
    
    struct node{
    	int x,y;
    };
    
    node a[10010];
    
    bool cmp(node n1,node n2){
    	return n1.x<n2.x || n1.x==n2.x&&n1.y>n2.y;
    }
    
    int main(){
    	int u,v;
    	int e;
    	cin>>n>>e;
    	for(int i = 1;i <= e;i++){
    		cin>>a[i].x>>a[i].y;
    	}
    	
    	sort(a+1,a+1+e,cmp);
    	for(int i = 1;i <= e;i++){
    		add(a[i].x,a[i].y);
    	}
    	
    //	for(int i = 1;i <= n;i++){
    //		cout<<pre[i]<<" ";
    //	} 
    //	cout<<endl;
    //	for(int i = 1;i <= n;i++){
    //		cout<<edge[i].u<<" "<<edge[i].v<<" "<<edge[i].next<<endl;
    //	} 
    	
    	print();
    	return 0;
    }
    
    
    • 1

    信息

    ID
    998
    时间
    1000ms
    内存
    512MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者