codeforces-794d-Labelling Cities-并查集缩点-哈希

题目链接

题意：给你一个n个点m条边（n,m<=3e5）的无向图，让你给n个点标号。标号按照如下规则：两个点的号码差的绝对值小于等于一当且仅当他们直接相连。

思路:可以分析（看题解）得到，如果两个点他们所连接的点完全相同，那么他们的标号一定相同。按照这个思路我们将所有连接点相同的点用并查集缩一下，同时缩完之后的图一定是一个单链，否则无解。所以我们找到一个度为1的点作为起点进行dfs。如果找不到度为1的点或者dfs中出现了环或者有点的度大于2那么无解。判断两个点的所有连接点是否相同时可以用hash。

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
using namespace std;
struct node
{
	int u,v;
}e[310005];
map<pair<int,int>,int>f;
long long pp[310005];
long long num[310005];
vector<int>g[310005];
vector<int>g2[310005];
int vis[310005];
int ans[310005];
int ans2[310005];
int vis2[310005];
int in[310005];
int n,m;
int cnt;
int fa[300005];
int fin(int x)
{
	if(x==fa[x])return x;
	 else return fa[x]=fin(fa[x]);
}
void un(int x,int y)
{
	int xx=fin(x);
	int yy=fin(y);
	fa[xx]=yy;
}
int flag=0;
int ok=0;
void dfs(int u,int ff,int z)
{
	ans2[u]=z;
	vis[u]=1;
	int l=g[u].size();
	flag=0;
	for(int i=0;i<l;i++)
	{
		int v=g[u][i];
		if(v!=ff)flag++;
		 else continue;
		if(vis[v]==1)
		{
			ok=1;
		 continue;
		}
		if(flag==2)
		{
		ok=1;
		return;
		}
		dfs(v,u,z+1); 
	}
}
int main()
{
	pp[0]=1;
	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)pp[i]=pp[i-1]*11LL;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=n;i++)
	{
		g[i].clear();
		g2[i].clear();
		//num[i]+=pp[i];
	}
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		e[i].u=u;
		e[i].v=v;
		num[u]+=pp[v];
		num[v]+=pp[u];
	}	
	for(int i=1;i<=m;i++)
	{
		int u=e[i].u;
		int v=e[i].v;
		if(num[u]-pp[v]==num[v]-pp[u])un(u,v);
	}
	for(int i=1;i<=m;i++)
	{
		int u=e[i].u;
		int v=e[i].v;
		u=fin(u);
		v=fin(v);
		
		if(u!=v && f[make_pair(min(u,v),max(u,v))]==0)
		{
			f[make_pair(min(u,v),max(u,v))]=1;
			//printf("%d %d\n",u,v);
			g[u].push_back(v);
			g[v].push_back(u);
			in[u]++;
			in[v]++;
		}
		
	}
	int cnt=0;
	for(int i=1;i<=n;i++)if(fin(i)==i)ans[i]=++cnt;
	for(int i=1;i<=n;i++)ans[i]=ans[fin(i)];
	ok=1;
	//for(int i=1;i<=n;i++)printf("fin:%d in:%d\n",fin(i),in[fin(i)]);
	for(int i=1;i<=n;i++)if(in[i]<=1 && fin(i)==i)
	{
		ok=0;
		//printf("root:%d\n",i);
		dfs(i,-1,1);
		break;
	}
	for(int i=1;i<=m;i++)
	{
		int u=e[i].u,v=e[i].v;
		u=fin(u);
		v=fin(v);
		if(abs(ans2[u]-ans2[v])>=2)ok=1;
	 	if(in[u]>=3 || in[v]>=3)ok=1;
	 } 
	if(ok)printf("NO\n");
	else
	{
		printf("YES\n");
		for(int i=1;i<=n;i++)printf("%d ",ans2[fin(i)]);
	}
	printf("\n");
	return 0;
}