萌萌哒的传送门
题目讲的是如何在一堆相亲的名单中找出有错误的地方,如两个同性的被安排相亲;
因为相亲的两个人必定是异性,所以题目可以转化为黑白染色问题.
何为黑白染色问题………………….
在一个无向图中,对图中所有的顶点染黑白俩色,并且要求共边的两个端点的颜色不能相同.
所以很容易想到直接dfs,对每一个还未染色的顶点进行染色,如果发现当前无法染成所需的,
则退出搜索.否则继续,注意图有可能不联通.
#include <iostream>#include <cstring>#include <cstdio>#include <cmath>#include <set>#include <map>#include <queue>#include <vector>#include <cstdlib>#include <algorithm>#define ls u << 1#define rs u << 1 | 1#define lson l, mid, u << 1#define rson mid + 1, r, u << 1 | 1#define INF 0x3f3f3f3fusing namespace std;typedef long long ll;const int M = 1e4 + 100;const int mod = 2147483647;int c[M];vector<int>G[M];bool dfs(int u) {for(int i = 0; i < G[u].size(); i++) {int co = G[u][i];if(c[co] == -1) {c[co] = c[u] ^ 1;if(!dfs(co)) return false;} else {if(c[co] == c[u]) return false;}}return true;}int main() {int T,n,m;cin>>T;while(T–) {scanf("%d %d",&n,&m);memset(c,-1,sizeof(c));while(m–) {int a,b;scanf("%d %d",&a,&b);G[a].push_back(b);G[b].push_back(a);}bool isGO = true;for(int i = 1; i <= n && isGO; i++) {if(c[i] == -1) {c[i] = 0;if(!dfs(i)) isGO = false;}}if(isGO) puts("Correct");else puts("Wrong");for(int i = 1; i <= n; i++) G[i].clear();}return 0;}
，绚丽的民族风情，悠久的历史文化。抛开尘世的纷扰，
