判断二分图的方法

题目描述：龙龙得知2020年中国将有2000万至4000万男人娶不到老婆后。他打算好好调查一下是不是人们的感情出现问题。他对n个人进行调查，得到m条信息，每条信息表示为某两人曾经是情侣。由于他不知道这些人的性别，请你帮他判断一下，有没有同性是情侣的情况？

对于100%的数据，n的范围[2,100000],m的范围[0,100000]。
解题思路：很裸的一个判断二分图的模板，主要是讲有几种方法可以判断二分图
1.dfs染色法：dfs所有的点，给每个相邻的点染色成0/1；相邻的两点颜色不相同，判断如果遇到已经被染色过的点，并且与上一个点的颜色一样，那就判断改图不是二分图。
2.影子并查集（扩展域并查集）：

1     for(int i=1;i<=2*n;i++)fa[i]=i;
2     for(int i=1;i<=m;i++){
3         scanf("%d%d",&x,&y);
4         int a=getfa(x),b=getfa(y);
5         int c=getfa(x+n),d=getfa(y+n);
6         if(a==b||d==c){f=false};
7         fa[a]=d;fa[b]=c;
8     }

如上，每个点都建立一个与之相对应的影子，将所有的点分成两个集合，对于一条边的两个端点，应该处于不同的集合中，分别将两个端点相应的影子端点放在分别与两端点相对的集合中，判断两个原端点或两个影子端点是否在一个集合中，如果在一个集合中，说明该图不是二分图。

3.带权并查集（核心思想：将两个相邻的点分成两类，用取模的思想快速判断是否是同一类端点）

注意事项（如图）帮助理解：