南阳理工学院ACM多乐赛暨16级退役纪念赛　C PK没有女朋友

题目来源：http://acm.nyist.edu.cn/problem/1663

题目描述:

因为 PK上个月没有去师范看她女朋友，所以PK 的女朋友最近又不理他了。异地恋实在是太辛苦了，理工到师范的距离，对于他来说，就像是驻马店到广州的距离。
曾有诗这样写道：
世上最遥远的距离，不是生与死的距离，不是天各一方，而是我就站在你面前，你却不知道我爱你。
PK决定要送给他的女朋友一条项链，希望能挽回女朋友的心，但他长期打 ACM 已经分辨不出什么是项链了，所以想请你帮帮他。
在眼中，他所买的东西就是个n个点和m条边构成的无向图（……）。判断这个图是不是项链，我们要做以下三件事情：
１.首先我们要在图上找一个环。而且我们要保证在图上只能找到这一个环。
2.环上可以长出一些树，这些树的根都在环上。树应该由至少一个节点组成，但为了美观起见，应该要能找到至少 3 棵树。
3.重边和自环是不允许出现的。不然女孩子有可能不小心把头伸进里面，然后出不来……
换句话说合格的图应该保证只有一个环，可以组成至少3课树，没有重边和自环。
如果满足以上三个条件，PK就会非常高兴，并大叫一声 Bingo。否则，他的女朋友就会和他分手……

输入描述:

第一行，给出 n,m (1 <= n <= 100, 0 <= m <= 10^5)。
接下来 m 行，每一行有两个整数 ui,vi (1 <= ui, vi <= n) 表示 ui 和 vi 之间有边相连。可能存在重边和自环。

输出描述:

如果是项链则输出 Bingo，否则输出 Break up。

样例输入:

样例输出:

Bingo
Break up

解法1
满足：
1.n==m
2.n>=3
3.没有重边和自环
就是项链
解法2
直接依照题意搜索(待补

/** 6 6 6 3 6 4 5 1 2 5 1 4 5 4 6 5 5 6 4 6 3 1 5 1 1 2 **/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#define ll long long
const int N=1e5+5;
#define inf 0x3f3f3f3f
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
struct node
{
    int n,m,k;
}xl[N];
int ans,sum,n,m,flag;
vector<int> tu[105];
ll a[105][105],b[105],check[105],vis[105];
void dfs(int x){
    for(int i=0;i<tu[x].size();i++){
        if(!vis[tu[x][i]]){
            vis[tu[x][i]]=1;
            check[tu[x][i]]=ans;
            dfs(tu[x][i]);
        }
    }
}
bool dfss(int x,int y){
    if(b[x]==1)
        sum++;
    if(xl[y].n-sum<3)
        return false;
    for(int i=0;i<tu[x].size();i++){
        if(!vis[tu[x][i]]){
            int k=tu[x][i];
            vis[k]=1;
            if(!dfss(k,y))
                return 0;
        }
    }
    return 1;
}
int main(){
    int x,y,i;while (cin>>n>>m) {
        mem(xl, 0);
        mem(a, 0);
        for (i = 1; i <= m; i++) {
            cin >> x >> y;
            if (a[x][y] == 0) {
                tu[x].push_back(y);
                tu[y].push_back(x);
            }
            a[x][y]++;
            a[y][x]++;
            b[x]++;
            b[y]++;
        }
        if (n != m || n < 3) {
            cout << "Break up" << endl;
            return 0;
        }
        vis[xl[i].k] = 1;
        mem(vis, 0);
        mem(check, 0);
        ans = 0;
        for (i = 1; i <= n; i++) {
            if (!vis[i]) {
                vis[i] = 1;
                ans++;
                check[i] = ans;
                dfs(i);
            }
        }
        for (i = 1; i <= n; i++) {
            int k = check[i];
            xl[k].n++;
            for (int j = 1; j <= n; j++) {
                xl[k].m += a[i][j];
            }
            xl[k].k = i;
        }
        flag = 0;
        for (i = 1; i <= ans; i++) {
            if (xl[i].n == xl[i].m / 2 && xl[i].n >= 3) {
                sum = 0;
                memset(vis, 0, sizeof(vis));
                vis[xl[i].k] = 1;
                if (dfss(xl[i].k, i)) {
                    flag++;
                }
            }
        }
        if (flag == 1) {
            cout << "Bingo" << endl;
        } else {
            cout << "Break up" << endl;
        }
    }
    return 0;
}