Rikka with Graph

Accepts: 123

Submissions: 525

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的：

给出一张 nn 个点 n+1n+1 条边的无向图，你可以选择一些边（至少一条）删除。

现在勇太想知道有多少种方案使得删除之后图依然联通。

当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？

输入描述

第一行一个整数表示数据组数 T(T \leq 30)T(T≤30)。

每组数据的第一行是一个整数 n(n \leq 100)n(n≤100)。

接下来 n+1n+1 行每行两个整数 u,vu,v 表示图中的一条边。

输出描述

对每组数据输出一行一个整数表示答案。

输入样例

输出样例

/*

BestCoder Round #73 (div.2)

hdu5631 Rikka with Graph 连通图 bfs or 并查集

思路：

总共有n+1条边，所以我们最多只需枚举两条边然后判断图是否是连通的即可

hhh-2016-02-25 11:27:16

*/

#include <functional>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <map>

#include <cmath>

#include <queue>

using namespace std;

typedef long long ll;

typedef long  double ld;

const int maxn = 105;

struct node

{

    int from,to,next;

} edge[maxn*2];

int vis[maxn*2];

int used[maxn];

int head[maxn*2];

int tot,n;

int ans;

void addedge(int u,int v)

{

    edge[tot].from = u;

    edge[tot].to = v;

    edge[tot].next = head[u];

    head[u] = tot++;

}

bool bfs()

{

    memset(used,0,sizeof(used));

    queue<int> q;

    q.push(1);

    used[1] = 1;

    while(!q.empty())

    {

        int t = q.front();

        q.pop();

        for(int i = head[t];i != -1;i = edge[i].next)

        {

            int v = edge[i].to;

            if(vis[i]) continue;

            if(used[v]) continue;

            used[v] = 1;

            q.push(v);

        }

    }

    for(int i =1;i <= n;i++)

    {

        if(!used[i])

            return false;

    }

    return true;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int x,y;

        scanf("%d",&n);

        memset(head,-1,sizeof(head));

        memset(vis,0,sizeof(vis));

        tot = 0;

        for(int i =1; i <= n+1; i++)

        {

            scanf("%d%d",&x,&y);

            addedge(x,y);

            addedge(y,x);

        }

        ans = 0;

        for(int i = 0; i <= n; i++)

        {

            for(int j = i+1; j <= n; j++)

            {

                vis[i*2] = vis[i*2+1] = 1;

                vis[j*2] = vis[j*2+1] = 1;

                if(bfs())

                ans++;

                vis[i*2] = vis[i*2+1] = 0;

                vis[j*2] = vis[j*2+1] = 0;

            }

        }

        //cout << ans <<endl;

        for(int i = 0; i <= n; i++)

        {

            vis[i*2] = vis[i*2+1] = 1;

            if(bfs())

                ans ++;

            vis[i*2] = vis[i*2+1] = 0;

        }

        printf("%d\n",ans);

    }

    return 0;

}

秒客网

hdu5631 BestCoder Round #73 (div.2)

Rikka with Graph

相关文章