[CF 542E] Playing on Graph

作法：

首先可以觀察到，如果圖中有三角形的話就是無解，因為不管怎麼樣這個三角形的三條邊都沒辦法消失。有了這個之後就可以進一步推到圖裡面沒有奇圈，因為當還存在一個奇圈時，如果圈上有兩個端點連了一條邊，那麼一定會分出一個比較小的奇圈，可以由數歸知道此時原圖無解，否則圈上的點兩兩不連邊，那麼我們遲早會選兩個圈上的點，把他們融合，這時候不難得到融合後一定會出現一個比較小的奇圈，也是由數歸得到此時無解，因此當原圖不是二部圖時就無解。

而當原圖為二部圖時顯然是有解的，因為由二部圖的定義，我們可以把節點群分為兩陀，使得同陀內的點兩兩不連邊，那麼這時只要把同一陀的點全部都融合起來就可以了，但當然他不會總是會是最佳的解，只是確定此時一定可以融合成一條鍊而已。再來則是當原圖不連通時，我們可以分別對每個連通塊求出他的答案再加起來，這就相當於把每個連通快都融合成一條鍊時，在把所有的鍊黏起來，不難知道這樣會是整張圖的最佳解，因此接下來只要考慮圖連通的情形，

假設現在已經把所有點都融合好形成一條練了，那麼每個新的圖中的節點都可以看成是由好幾個舊的圖中的點融合在一起得到的。例如 $A$ 和 $B$ 融合之後的新節點再去和 $C$ 融合，那麼所得到的節點就可以看成 $ABC$ 三點融合在一起的點，並且必須滿足這$3$個點兩兩之間沒有連邊。因此如果我們把新得到的圖的所有節點都「展開」回舊的圖的節點，就會變成長的像類似下面這張圖的東西

其中落在同一陀裡的點兩兩之間沒有連邊，他們在新的圖中會融合成一個點。而這張圖就類似我們在找單源最短路時，以某個點為源點所畫出來的層次圖（把所有點按照他和源點的距離分成不同的幾組），而事實上用任意一個點為源點畫出來的層次圖的確可以滿足這邊的條件，因為現在的圖是二部圖，所以可以保證這樣子分組不會讓同組中的任兩個點相鄰。因此就得到了這題的演算法：對於每個連通分量，對於裡面的每個點都做一次BFS，求出離他最遠點的距離，而在這些距離中的最大值就是這個連通分量的答案，再把所有連通分量的答案加起來即可。


code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10 ;
 
vector<int> v[maxn] ;
int col[maxn] ;
bool dfs(int x,int c)
{
    col[x]=c ;
    for(auto i : v[x])
    {
        if(col[i]==-1 && !dfs(i,c^1)) return 0 ;
        else if(col[i]!=-1 && col[i]==c) return 0 ;
    }
    return 1 ;
}
 
bool vis[maxn] ;
int tmp[maxn],d[maxn],cnt ;
 
queue<int> q ;
int BFS(int x,int type)
{
    int ret=0 ;
    memset(d,-1,sizeof(d)) ;
    q.push(x) ; d[x]=0 ;
    while(!q.empty())
    {
        int u=q.front() ; q.pop() ;
        ret=max(ret,d[u]) ;
        if(type==1) tmp[cnt++]=u ;
        for(auto i : v[u]) if(d[i]==-1)
            d[i]=d[u]+1 , q.push(i) ;
    }
    return ret ;
}
 
int solve(int x)
{
    int ret=0 ;
    cnt=0 ;
    for(int st=x,i=1;;i++)
    {
        ret=max(ret,BFS(st,st==x)) ;
        if(i==cnt) break ;
        st=tmp[i] ;
    }
    for(int i=0;i<cnt;i++) vis[tmp[i]]=1 ;
    return ret ;
}
 
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    while(m--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
 
    memset(col,-1,sizeof(col)) ;
    for(int i=1;i<=n;i++) if(col[i]==-1 && !dfs(i,0))
        {printf("-1\n") ; return 0 ;}
 
    int ans=0 ;
    for(int i=1;i<=n;i++) if(!vis[i]) ans+=solve(i) ;
    printf("%d\n",ans) ;
}