题意
[SHOI2015]零件组装机：https://www.luogu.com.cn/problem/P4386
做法
同机房大佬想性质想了很久，我从树的思想搞很快搞出来了
言归正传，这道题目从树的思路想是比较简单的，关键是建树。
现在讲讲建树：对于一条边，默认是从编号大的连向编号小的有向边。
那么，设 $x$ 连向的编号最大的点为 $y$，那么 $x,y$ 是什么关系？
我们规定一个联通块的根为这个联通块编号最小的点（不难发现联通块的编号是连续的），那么 $x,y$ 的关系其实就是以 $x$ 为根的联通块与 $[y,x-1]$ 的联通块合并。
这样，我们就只需要根据 $x,y$ 建出一棵树，从下往上合并，每次合并检验一下即可。
需要注意的是：如果存在重边和自环直接无解。
当然还有一个性质：合法图的边的是在 $O(n)$ 级别的。（同机房大佬找到的）
时间复杂度：$O((n+m)\log{m})$
用桶排加内存池以及其余细节便可以优化到 $O(n+m)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| #include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#define N 110000
using namespace std;
set<int> fuck[N];
int cnt,now;
int fa[N],siz[N];
int id[N];
inline bool cmp(int x,int y){return siz[x]<siz[y];}
inline bool check(int l1,int r1,int l2,int r2)
{
int n=r1-l1+1,m=r2-l2+1;
if(n>m)return 1;
for(int i=0;i<m;i++)
{
int x=l1+i%n,y=l2+i;
set<int>::iterator z=fuck[y].find(x);
if(z==fuck[y].end())return 1;
now++;
fuck[y].erase(z);
}
return 0;
}
int n,m;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
now=cnt=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)fuck[i].clear();
bool bk=0;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(x<y)x^=y^=x^=y;
if(bk)continue;
if(x==y){bk=1;continue;}
set<int>::iterator shit=fuck[x].find(y);
if(shit==fuck[x].end())
{
fuck[x].insert(y);
cnt++;
}
else bk=1;
}
for(int i=0;i<n;i++)id[i]=i;
siz[0]=1;
for(int i=1;i<n;i++)
{
siz[i]=1;
if(!fuck[i].size())
{
bk=1;
break;
}
set<int>::iterator x=fuck[i].end();
x--;fa[i]=*x;
}
if(bk==1){printf("NO\n");continue;}
for(int i=n-1;i>=1;i--)siz[fa[i]]+=siz[i];
sort(id,id+n,cmp);
for(int i=0;i<n-1;i++)
{
int x=id[i],y=fa[x];
if(check(y,x-1,x,x+siz[x]-1))
{
bk=1;
break;
}
}
if(bk==1 || now!=cnt){printf("NO\n");continue;}
printf("YES\n");
}
return 0;
}
|
