CF542E Playing on Graph 题解

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

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

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

 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


#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);
}