CF542E Playing on Graph 题解

首先如果是一个三角形，那它们一定不能变成一条链。其次，如果是任意一个奇环，那每次任意缩掉两个点，最终都会变成三角形。因此奇环是不可能变成链的。

一个没有奇环的图，一定为二分图。对于每一个联通块，我们以某点为根BFS分层，由于是二分图分成的每一层的点都没有边相互联通，所以可以缩成一点。

找出每个联通块的最长链，由于最长链可以首尾相连合并，因此答案为所有最长链长度之和。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const LL MAXN=1005,MAXM=100005;
vector<LL>a[MAXN];
LL n,m;
LL bel[MAXN],col[MAXN],cnt;
void dfs(LL x){bel[x]=cnt;LL len=a[x].size();for(LL i=0;i<len;i++){LL xx=a[x][i];if(!bel[xx])col[xx]=col[x]^1,dfs(xx);else if(col[xx]==col[x]){printf("-1");exit(0);}}
}
LL dis[MAXN],ans[MAXN];
queue<LL>q;
void bfs(LL x){memset(dis,-1,sizeof(dis));dis[x]=0;q.push(x);while(!q.empty()){LL t=q.front();q.pop();for(LL i=0;i<a[t].size();i++){LL xx=a[t][i];if(dis[xx]==-1){dis[xx]=dis[t]+1;q.push(xx);}}}
}
int main(){scanf("%lld%lld",&n,&m);for(LL i=1;i<=m;i++){LL u,v;scanf("%lld%lld",&u,&v);a[u].push_back(v);a[v].push_back(u);}for(LL i=1;i<=n;i++){if(!bel[i]){cnt++;dfs(i);}}for(LL i=1;i<=n;i++){bfs(i);for(LL j=1;j<=n;j++){ans[bel[i]]=max(ans[bel[i]],dis[j]);}}LL sum=0;for(LL i=1;i<=cnt;i++){sum+=ans[i];}printf("%lld",sum);
}