【题目链接】：
【题目大意】：
给出N个人和M对关系，表示a和b认识，把N个人分成两组，同组间随意俩人互不认识。若不能分成两组输出No，否则输出两组间俩人互相认识的对数
【解题思路】: 先推断是否能构成二分图，推断二分图用交叉染色法：从某个未染色的点出发把此点染成白色，该点周围的点染成黑色。黑色周围的又染成白色。若走到某个点已经染色，而且它相邻点的颜色与它一样则不是二分图，能够这样理解，染白色既增加X集合，黑色既增加Y集合，若某个点即是X集合又是Y集合，那说明不是二分图，推断二分图之后，再求最大的匹配数。PS：二分图是无向图时最大匹配数是Sum/2。代码：
#pragma comment(linker, "/STACK:1024000000,1024000000")#include#include #include #include #include #include #include #include #include #include #include #include #include #include #include // C++#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include
#include
a:b #define Min(a,b) a>b?b:a #define mem(a,b) memset(a,b,sizeof(a)) int dir4[4][2]= {
{1,0},{0,1},{-1,0},{0,-1}}; int dir8[8][2]= { {1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}}; int movv[5][2]= { {1,0},{0,1},{0,0},{-1,0},{0,-1}}; using namespace std; typedef long long LL; typedef unsigned long long LLU; typedef double db; const int inf=0x3f3f3f3f; const int N =205; int head[N],link[N];///邻接表 bool vis[N],col[N]; int cnt,n,m; inline LL read() { int c=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} return c*f; } struct edge{ int to; int next; }g[N*N]; void init(){ cnt=0; mem(head,-1); mem(col,0); } void add_edge(int u,int v){ g[cnt].to=v; g[cnt].next=head[u]; head[u]=cnt++; } bool color(int u){ ///染色 for(int i=head[u]; i!=-1; i=g[i].next){ int v = g[i].to; if(!col[v]){ col[v] = !col[u]; if(!color(v)) return false; } else if(col[v]==col[u]) return false; } return true; } bool dfs(int u) ///匈牙利算法dfs实现 { for(int i=head[u]; i!=-1; i=g[i].next){///元素集合个数 int v=g[i].to; if(!vis[v]){ vis[v]=1; if(link[v]== -1|| dfs(link[v])){ link[v]=u; return true; } } } return false; } int match() ///最大匹配 { int ans = 0; mem(link,-1); for(int i=1; i<=n; ++i){ mem(vis,0); if(dfs(i)) ans++; } return ans; } int main() { while(~scanf("%d%d",&n,&m)){ if(n==1){ puts("No"); continue; } init(); while(m--){ int u,v; u=read(),v=read(); add_edge(u,v); add_edge(v,u); } col[1]=1; if(!color(1)) puts("No"); else printf("%d\n",match()>>1); } return 0; }