B3613 图的存储与出边的排序

· · 题解

看到其他题解用的都是 vector，这里提供一种不一样的思路：用 STL 中的 set 来存图。

解题思路：

我们考虑使用 set<int>s[maxn] 以邻接表的格式存储图。每读取一条边，就用 s[x].insert(y); 存进去。在输出的时候，我们就可以直接输出 s_i 中存储的所有终点了。

set 相比 vector 有一个优势：在插入的时候，它就能够自动去重和排序。也就是说，在插入完毕之后，我们无需像 vector 一样用 sort 扫一遍了。

关于 set 的基本操作：

1.插入

insert(x) 用于将 x 插入到 set 中，并自动递增排序和去重。时间复杂度为 O(\log_2 n)，其中 n 为 set 中的元素个数。

2.获取元素个数。

size() 用来获得 set 中的元素个数，时间复杂度为 O(1)。

3.清空元素

clear() 用来清空 set 中的所有元素，时间复杂度为 O(n)。

4.删除指定元素

erase() 可以删除单个元素，也可以删除一个区间内的所有元素。删除单个元素时可以使用 erase(it)，其中 it 为要删除的元素的迭代器，时间复杂度为 O(1)。也可以使用 erase(x)，其中 x 为要删除元素的值，时间复杂度为 O(\log_2 n)。例如以下一段代码（若 s 为已定义好的 set 集合）：

s.insert(1);
s.insert(10);
s.insert(100);
s.erase(10);
for(set<int>::iterator it=s.begin();it!=s.end();it++)cout<<*it<<' ';

其输出结果为 1 100。

5.找到对应元素

find(x) 返回的是 set 中对应值为 x 的迭代器，时间复杂度为 O(\log_2 n)。例如以下一段代码：

s.insert(1);
s.insert(2);
s.insert(3);
printf("%d",*(s.find(2)));

其输出结果为：2

在了解了 set 的基本用法之后，我们来看一看本题的代码：

Code:

#include<cstdio>
#include<set>//set专属头文件
using namespace std;
const int maxn=5e5+5;
int t,n,m,x,y;
set<int>s[maxn];
inline int read(){//快读
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-48,ch=getchar();
    return s*w;
}
inline void write(int x){//快写
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+48);
}
int main(){
    t=read();
    while(t--){
        n=read();m=read();
        for(int i=1;i<=n;i++)s[i].clear();//在一组数据的开始部分进行初始化，将集合清空。
        for(int i=1;i<=m;i++){
            x=read();y=read();
            s[x].insert(y);//使用邻接表的方式存储图。
        }
        for(int i=1;i<=n;i++){
            for(auto it=s[i].begin();it!=s[i].end();it++)
                write(*it),putchar(' ');//遍历输出
            putchar('\n');//注意：即使一行中没有输出也要换行
        }
    }return 0;
}