http://acm.hdu.edu.cn/showproblem.php?pid=1829 题意:
给出 n 个虫子之间的 m 对关系, 要求每对关系的两个虫子是不同性别. 问给出的 m 对关系中是否出现冲突.
emm…看有题解写分组并查集, 想了想感觉好麻烦. 数据范围 n <= 2000, m <= 1e6, TimeLimit 5000ms 把每个虫子看作一个点, 每个关系是一条边, 判断一下二分图就好
dfs代码 (800ms)
#include <stdio.h> #include <iostream> #include <cstring> using namespace std; const int MAX = 2017; bool mp[MAX][MAX], KEY; int pnt[MAX]; unsigned int T, n, m, I, fm, to; void getin() { memset(mp, 0, sizeof(mp)); memset(pnt, 0, sizeof(pnt)); KEY = true; scanf("%u%u", &n, &m); for (int i = 0; i < m; ++i) { scanf("%u%u", &fm, &to); mp[fm][to] = 1, mp[to][fm] = 1; } } void dfs(int now, int colour) { if (pnt[now]) { if (pnt[now] != colour) KEY = false; return ; } pnt[now] = colour; for (int i = 1; KEY && i <= n; ++i) { if (i == now) continue; if (mp[now][i]) dfs(i, 3-colour); } return ; } void judge() { for (int i = 1; KEY && i <= n; ++i) { if (pnt[i]) continue; dfs(i, 1); } printf("Scenario #%d:\n", I); if (!KEY) printf("S"); else printf("No s"); printf("uspicious bugs found!\n\n"); } int main() { // freopen("in.in", "r", stdin); // freopen("out.out", "w", stdout); scanf ("%u", &T); for (I = 1; I <= T; ++I) { getin(); judge(); } }2017.08.31
