题目

思路

思路一定要开阔……我一开始 $\tt yy$ 了个什么做法哟……

我一开始直接猜是 $\tt dfs$ 树这种线性的东西。然后开始努力的优化。首先思考到 “异色边” 只需要走过一次，因为一旦走过这个 “异色边” ，只要你认真地深搜，就会搜出这个环。但是 “同色边” 就不行了，所以考虑同色连通块缩点，缩成两个点即可（因为我们只在乎环的奇偶）。

然后一个点会被访问很多次。考虑把边排序后 $\tt lower\_bound$ ，发现仍然不行，复杂度假了。于是考虑直接把所有同类的异色边拿出来。此时才发现是 并查集。

意识到带权并查集可以处理二分图之后，一切问题都解决了，只需要一个可回退的并查集就行。但是我在这里吃了个教训：回退不能改变树结构，必须是按秩合并。一旦路径压缩你就完蛋了。 $\mathcal O(n\log n)$ 。

当然，如果你把连通块缩点了，你也可以路径压缩，把所有波及到的连通块暴力连接回去。可以优化到 $\mathcal O(\alpha n)$ ，但是我们并不需要这么优秀 😂

$\tt 2020/12/4\;update$

突然意识到原本的做法完！全！可！行！（指同色连通块缩成两个点）

为啥一定要在原图上跑 $\tt dfs$ 树？我们姑且把边放在 $\tt vector$ 里，每次用链式前向星加入有用的边然后造 $\tt dfs$ 树不就行了？这不就是线性的了？这不就是 $\mathcal O(n+m)$ 随便跑？

缩点也并不麻烦，每个连通块内随便找个点，然后到它距离为奇数和偶数的分到两边。

我感觉我真是蠢到爆炸……全地球可能很难找出一个像我一样蠢的蠢货了！

代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long int_;inline int readint(){   	int a = 0; char c = getchar(), f = 1;	for(; c<'0'||c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c&&c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}const int MaxN = 500005;struct UFS{   	vector< int > zxy; // fucked	int fa[MaxN], d[MaxN];	int rnk[MaxN]; // 启发式合并	inline int find(int a,int &x){   		if(a == fa[a]) return a;		return find(fa[a],x ^= d[a]);	}	void init(int n){   		for(int i=1; i<=n; ++i){   			fa[i] = i, d[i] = 0;			rnk[i] = 1;		}		zxy.clear();	}	/** @return 是否仍然为二分图 */	inline bool merge(int a,int b){   		int da = 0, x = find(a,da);		int db = 0, y = find(b,db);		if(x == y) return da != db;		if(rnk[x] > rnk[y]) swap(x,y);		fa[x] = y, d[x] = da^db^1;		rnk[y] += rnk[x]; // ensure Complexity		zxy.push_back(x); return true;	}	void restore(){   		while(!zxy.empty()){   			int x = zxy.back();			rnk[fa[x]] -= rnk[x];			fa[x] = x, d[x] = 0;			zxy.pop_back();		}	}};UFS xyx; // 并查集vector< pair
       
         > cu; // 不铜的边int col[MaxN]; // 每个点的颜色bool cmp(const pair
        
          &a,const pair
         
           &b){ if(col[a.first] != col[b.first]) return col[a.first] < col[b.first]; return col[a.second] < col[b.second];}bool junk[MaxN]; // 不行的颜色int main(){ int n = readint(), m = readint(); int k = readint(); for(int i=1; i<=n; ++i) col[i] = readint(); xyx.init(n); // 同色连通块直接连出来 for(int i=1,a,b; i<=m; ++i){ a = readint(), b = readint(); if(col[a] == col[b]) junk[col[a]] = junk[col[a]] or !xyx.merge(a,b); else{ if(col[a] > col[b]) swap(a,b); // 使其无序 cu.push_back(make_pair(a,b)); } } xyx.zxy.clear(); // 把 zxy 清空 sort(cu.begin(),cu.end(),cmp); int_ ans = 0; // 最终答案 for(int i=1,now=0; i<=k; ++i) if(!junk[i]) // 垃圾颜色跳过 ans += now, ++ now; for(int l=0,r=0,len=cu.size(); l

转载地址：http://oitq.baihongyu.com/

你可能感兴趣的文章