cf 542E - Playing on Graph

题目大意

给定一个\(n\le 1000\)个点的图

求经过一系列收缩操作后能否得到一条链，以及能得到的最长链是多长

收缩操作：

选择两个不直接相连的点，构造一个新点

对于原图中的每一个点，如果它与这两个点中的任意一个有连边

那么它向这个新点连一条边

最后删除选择的两个点，以及所有这两个点的连边

分析

注意到对于一个奇环，无论怎么收缩，都会产生一个新的奇环，最后奇环变成一个三角形，再也缩不了，永远无法变成一条链

只有偶环的图是二分图

对于图中的一个子图，它是二分图，我们就能构造一组解

选择一个点作为起点，从该点出发得到一棵\(bfs\)树

由于是二分图，\(bfs\)树同一层节点之间没有连边

由于是\(bfs\)树，每个点的连边只能在相邻一层的范围内，且必定和上一层节点有连边

那么我们把同一层节点缩在一起，就可以得到一条链

按照这种方法，图的直径就是答案（图的直径为最短路中的最大值）

直径时最优解可以用归纳法证明：

对于\(1\)个点的任意图显然成立

假设对于\(n\)个点的任意图成立，那么对于\(n+1\)个点的任意图

如果图中不存在环，那么是一棵树，直径显然是答案

否则，至少进行一次收缩，则答案为缩掉一对点后的直径中最大是多少

缩掉一个点后的直径一定不比原来的直径大

而原来的直径能构造出一组解

连通块间的答案是相加的：

对于图中的所有联通块，每块缩成一条链后，链可以两两合并

做法

先判断是不是二分图

然后每个联通块求一次图的直径

然后所有联通块的答案加起来

图的直径求法是每个点出发跑一次\(bfs\)

solution

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int M=1007;const int N=1e5+7;inline int ri(){ int x=0;bool f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=0; for(;isdigit(c);c=getchar()) x=x*10+c-48; return f?x:-x;}int n,m;struct vec{ int g[M],te; struct edge{ int y,nxt; edge(int _y=0,int _nxt=0){y=_y,nxt=_nxt;} }e[N<<1]; vec(){memset(g,0,sizeof g);te=0;} inline void push(int x,int y){e[++te]=edge(y,g[x]);g[x]=te;} inline void push2(int x,int y){push(x,y);push(y,x);} inline int& operator () (int x){return g[x];} inline edge& operator [] (int x){return e[x];}}e;int vis[M],ok,ans;vector
           
            pt;int d[M];void dfs(int x){ int p,y; for(p=e(x);p;p=e[p].nxt){ y=e[p].y; if(!vis[y]){ vis[y]=3-vis[x];//1->2 2->1 dfs(y); } else if(vis[y]!=3-vis[x]) ok=0; }}bool chk(){ ok=1; memset(vis,0,sizeof vis); for(int i=1;i<=n;i++) if(!vis[i]) vis[i]=1,dfs(i); return ok;}int gao(int bg){ static int q[M]; int h=0,t=1,x,p,y,i,mx=0; for(i=0;i