[原创]HDU1829&POJ 2492 a bug’s life [并查集||二分图染色]

2016-03-10 17:36:49 Tabris_ 阅读数：461

博客爬取于2020-06-14 22:44:53
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/50848661

##POJ 2492 a bug’s life [并查集||二分图染色]

题目链接:POJ<-点此进入链接 HDU<-点此进入链接

A Bug’s Life
Time Limit: 10000MS Memory Limit: 65536K
Total Submissions: 32887 Accepted: 10772
Description

Background
Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs.
Problem
Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it.
Input

The first line of the input contains the number of scenarios. Each scenario starts with one line giving the number of bugs (at least one, and up to 2000) and the number of interactions (up to 1000000) separated by a single space. In the following lines, each interaction is given in the form of two distinct bug numbers separated by a single space. Bugs are numbered consecutively starting from one.
Output

The output for every scenario is a line containing “Scenario #i:”, where i is the number of the scenario starting at 1, followed by one line saying either “No suspicious bugs found!” if the experiment is consistent with his assumption about the bugs’ sexual behavior, or “Suspicious bugs found!” if Professor Hopper’s assumption is definitely wrong.
Sample Input

2
3 3
1 2
2 3
1 3
4 2
1 2
3 4
Sample Output

Scenario #1:
Suspicious bugs found!

Scenario #2:
No suspicious bugs found!
Hint

Huge input,scanf is recommended.

题目大意 :就是让虫子a与虫子b交配 不能同性交配 输入的数是两个虫子的序号 就是交配的两个虫子 如果性别相同了 就输出"Suspicious bugs found!" 否则输出"No suspicious bugs found!"…

Ps: 这题目 污的不是一星半点…

并查集

先说一说并查集吧

就是说利用并查集的父子节点来表示不同的性别 ,

要注意的是 每颗树上 先确定父节点的性别 以此来判断子节点的性别就行 差一辈的就是异性 差两辈的就是同性
之后在建一个数组来存储性别 可以定义0是一个性别 1是另一个性别 在join函数中 如果处理的两个节点 在同一颗树上 且同性 就是"Suspicious bugs found!" 其他情况 就是"No suspicious bugs found!"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
const int M= 1005;
const int MAX= 100005;
const long long int MOD=1000000007;
using namespace std;
int pre[MAX];
int vis[MAX],n,m;
int color[MAX];//0  一个性别  1另一个性别
int ans=1,cnt,q,flag;
void ff(int n)
{
    for(int i=1; i<=n; i++)
    {
        pre[i]=i;
    }
    memset(color,0,sizeof(color));
    return ;
}

int findi(int x)    //理解，加强理解
{
    int rt;
    if(x!=pre[x])
    {
        rt=findi(pre[x]);
        color[x]=color[x]^color[pre[x]];
        return pre[x]=rt;
    }
    return pre[x];
}

void join(int x,int y)
{
    int fx=findi(x),fy=findi(y);
    if(fx==fy)
    {
        ans=color[x]^color[y];
    }
    else
    {
        pre[fx]=fy;
        color[fx]=~(color[x]^color[y]);
    }

}

int main()
{
    int t,f=0;
    scanf("%d",&t);
    while(t--)
    {
        if(f==1)   printf("\n");
        f=1,ans=1;
        scanf("%d%d",&n,&m);
        ff(n);
        int a,b;
        for(int i=0;i<m;i++)
        {
            scanf("%d %d",&a,&b);
            if(ans)
            join(a,b);
        }

        printf("Scenario #%d:\n",++q);
        if(!ans)
            printf("Suspicious bugs found!\n");
        else
            printf("No suspicious bugs found!\n");

    }
    return 0;
}

二分图染色

二分图染色来自于此

稍后 就贴上

昨天一天就弄着一道题了。

一开始的时候想法是判断是否存在奇数圈。如果存在，肯定有同性恋存在。

后来看到了别人的想法。就是，判二分图。

后来在，上课翻离散书的时候看到一个定理：n阶无向图是一个二分图当且仅当图中没有无奇数圈。

这样，判奇数圈和判二分图就是一个意思了。

那么，怎么来判奇数圈或者二分图呢？？？

搜索了一下，看到一种染色法判断二分图。意思就是，将图中的节点染色，如果能够把所有的点染成不同的两个颜色，并且不产生矛盾（相连的节点颜色相同）；

如图所示：
这里写图片描述这里写图片描述

可以用BFS或DFS实现：

BFS：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# include <vector>
# include <queue>
# define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;

const int N=2005;
int color
,n,m;
bool vis
;
vector<int> map
;

bool bfs(int s){
    queue<int> q;
    q.push(s);color[s]=1;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=1;i<=10000000;i++);
        printf("now %d\n",now);
        if(!vis[now]){
        int len=map[now].size();
        for(int i=0;i<len;i++){
            int des=map[now][i];
            q.push(des);
            if(color[des]==-1)
            color[des]=color[now]==0?1:0;
            else {
                if(color[des]==color[now]) return false;
                else continue;
            }
        }
        vis[now]=true;
        }
    }
    return true;
}

int main(){
    freopen("1.txt","r",stdin);
    int T,k=1;
    scanf("%d",&T);
    while(T--){
        CLR(color,-1);CLR(vis,0);
        CLR(map,0);
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            map[a].push_back(b);
            map[b].push_back(a);
        }
        int i;
        printf("Scenario #%d:\n",k++);
        for(i=1;i<=n;i++){
            if(!vis[i]){
                bool flag=bfs(i);
                if(!flag){
                    printf("Suspicious bugs found!\n\n");
                    break;
                }
            }
        }
        if(i>n) printf("No suspicious bugs found!\n\n");
    }
    return 0;
}

DFS：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# include <vector>
# define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;

const int N=2003;
int n,m,color
;
vector<int> map
;
bool vis
;

bool dfs(int s){
    vis[s]=true;
    int len=map[s].size();
    for(int i=0;i<len;i++){
        int des=map[s][i];
        if(color[des]==color[s]) return false;
        if(color[des]==-1){
            color[des]=color[s]==0?1:0;
            if(!dfs(des)) return false;
        }
    }
    return true;
}
int main(){
    freopen("1.txt","r",stdin);
    int T,k=1;
    scanf("%d",&T);
    while(T--){
        CLR(map,0);
        CLR(vis,0);CLR(color,-1);
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            map[a].push_back(b);
            map[b].push_back(a);
        }
        printf("Scenario #%d:\n",k++);
        bool flag=false;
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                color[i]=1;
                if(!dfs(i)){
                    flag=true;
                    break;
                }
            }
        }
        if(flag) printf("Suspicious bugs found!\n\n");
        else printf("No suspicious bugs found!\n\n");
    }
    return 0;
}

无论BFS还是DFS，需要注意的是，所有的节点可能出现在不同的集合中。需要多次BFS或DFS。

二分图染色来自于此