目录
codeforces 794D Labelling Cities题意题解Ｃｏｄｅ
codeforces 794D Labelling Cities
题目传送门
题意
给出一个\(n\)个点\(m\)条边的图，要求给图中的每一个点赋一个值\(x[i]\)，使得任意两个点之间有边当且仅当\(|x[i]-x[j]|<=1\)。问是否存在满足条件的方案，如果有，输出每个点的值。\((2\leq n \leq 3*10^5,1 \leq m \leq 3*10^5)\)
题解
这个题目需要一些脑洞。总共需要想到两个结论： １.对于一些没有边直接相连的点，如果另一个点连接了超过２个这些点，那么肯定就是无解的。 ２.如果对于两个点，他们相邻的点（包括自己）所组成集合相同，如果题目有解，那么一定会有一种合法方案中，这两个点的值相同。 想到这两个点差不多就可以做出来了。第一个比较好证明，因为如果一个点连接了两个以上互不相连的点，那么这些点当中一定会有两个点的\(x\)值差值小于等于１，并且之间没有边相连。这个画画图理解一下就很容易的出来了。重点在于第二个，由于这两个点的相连的点都是相同的，那么这两个点和他们连接的那些点的差值都是相同的，所以我们将这两个点的值赋为相同的也是合法的。于是我们可以借助第二个结论，用哈希将所有值相同的点都缩在一起，这样剩下来的就是值不相同的点了。再根据第一个点，我们可以知道这个缩完点的图一定是一条链了，然后我们从链顶开始赋值就行了。
Ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const int M=3e5+500;
int n,m,Base=13131;
std::vector<int>G[M],F[M];
ll H[M];
int idx[M],fa[M],res[M];
typedef std::vector<int>::iterator vit;
/*==================Define Area================*/
ll Hash(int x) {
sort(G[x].begin(),G[x].end());
ll res=0;
for(vit it=G[x].begin();it!=G[x].end();++it) {
res=res*Base+*it;
}
return res;
}
bool cmp(int a,int b) {return H[a]<H[b];}
int main() {
read(n);read(m);
for(int i=1;i<=n;i++) G[i].push_back(i);
for(int i=1,u,v;i<=m;i++) {
read(u);read(v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;i++) H[i]=Hash(i),idx[i]=i;;
sort(idx+1,idx+1+n,cmp);
for(int i=1;i<=n;i++) {
int x=idx[i],y=idx[i-1];
fa[x]=(H[x]!=H[y])?x:fa[y];
}
for(int i=1;i<=n;i++) {
for(vit it=G[i].begin();it!=G[i].end();++it) {
int j=*it;
if(fa[i]!=fa[j]) F[fa[i]].push_back(fa[j]);
}
}
int st;
for(int i=1;i<=n;i++) {
if(fa[i]!=i) continue ;
sort(F[i].begin(),F[i].end());
F[i].erase(unique(F[i].begin(),F[i].end()),F[i].end());
if(F[i].size()>2) return puts("NO"),0;
if(F[i].size()<=1) st=i;
}
queue<int>Q;
Q.push(st);
res[st]=1;
while(!Q.empty()) {
int o=Q.front();Q.pop();
for(vit it=F[o].begin();it!=F[o].end();++it) {
if(!res[*it]) Q.push(*it),res[*it]=res[o]+1;
}
}
puts("YES");
for(int i=1;i<=n;i++) {
printf("%d ",res[fa[i]]);
}
puts("");
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9556486.html
