ｄｆｓ找出连通块 块内构造数据 ｂｆｓ找出最值
如果有多个连通块 那ｍａｘ就为４９ 可以起点不同 这样记得修改后面的数据
写的老长了。。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<queue>
using namespace std;
vector<int>ed[];
int vis[],gg,p,g,maxz,o[],pp[][],q[];
int w[],mm[];
void dfs(int u)
{
gg++;
pp[g][gg] = u;
int i;
for(i = ; i < (int)ed[u].size() ; i++)
{
int k = ed[u][i];
if(!o[k])
{
o[k] = ;
dfs(k);
}
}
}
int bfs(int u,int k)
{
int i,tt=;
for(i = ; i <= q[k] ; i++)
{
vis[pp[k][i]] = ;
}
queue<int>qq;
qq.push(u);
vis[u] = ;
while(!qq.empty())
{
int k = qq.front();
tt = max(vis[k],tt);
qq.pop();
for(i = ; i < (int)ed[k].size() ; i++)
{
int v = ed[k][i];
if(vis[v]>)
return -;
if(vis[v]&&abs(vis[v]-vis[k])!=)
{
return -;
}
if(!vis[v])
{
vis[v] = vis[k]+;
qq.push(v);
}
}
}
if(maxz<tt)
{
maxz = tt;
mm[k] = maxz;
for(i = ; i <= q[k] ; i++)
{
w[pp[k][i]] = vis[pp[k][i]];
}
}
return ;
}
int main()
{
int n,i,j;
scanf("%d%d",&n,&p);
for(i = ; i <= n ; i++)
{
int u,v;
scanf("%d%d",&u,&v);
ed[u].push_back(v);
ed[v].push_back(u);
}
g = ;
for(i = ; i <= p ; i++)
{
if(!o[i])
{
o[i] =;
dfs(i);
q[g] = gg;
gg=;g++;
}
}
int nu=;
for(i = ; i < g ; i++)
{
int kk=;
maxz=;
for(j = ; j <= q[i] ; j++)
{
if(bfs(pp[i][j],i)>)
{
kk=;
}
}
if(!kk)
{
maxz=;
break;
}
}
if(maxz==)
printf("-1\n");
else
{
if(g>)
{
printf("49\n");
for(i = ; i <= q[] ; i++)
w[pp[][i]]+=(-mm[]);
}
else
{
printf("%d\n",maxz-);
}
for(i = ; i <= p ; i++)
printf("%d ",w[i]);
puts("");
}
return ;
}