Rikka with Graph

Accepts: 123 Submissions: 525 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) 问题描述

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

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

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

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

输入描述

第一行一个整数表示数据组数  $\leq 30)$ 。

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

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

输出描述

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

输入样例

输出样例

题解：

Rikka with Graph

让 $n$ 个点联通最少需要 $n - 1$ 条边，所以最多只能删除两条边，我们可以枚举删除的这两条边（或者唯一的一条边），然后暴力BFS判断连通性就好了。时间复杂度 $O(n^3)$ 。

并查集AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<queue>
#include<vector>
#include<set>
using namespace std;
const int T=5000;
#define inf 0x3f3f3f3fL
#define mod 1000000000
typedef long long ll;
typedef unsigned long long ULL;

int n,m,i,j,k;
int arr[110];

struct node 
{
int l,r;
}a[110];

void Init()
{
for(i=0;i<=m;++i){
arr[i] = i;
}
}

int fi(int x)
{
return arr[x]!=x?arr[x]=fi(arr[x]):x;
}

void find(int x,int y)
{
int tx = fi(x),ty = fi(y);
if(tx!=ty){
arr[tx] = ty;
}
}

bool fun()
{
k = fi(1);
for(i=2;i<=m;++i){
if(k!=fi(i))
return false;
}
return true;
}

bool judge(int x)
{
Init();
for(i=0;i<=m;++i){
if(i!=x){
find(a[i].l,a[i].r);
}
}
return fun();
}

bool judge(int x,int y)
{
Init();
for(i=0;i<=m;++i){
if(i!=x&&i!=y){
find(a[i].l,a[i].r);
}
}
return fun();
}

int main()
{
#ifdef zsc 
freopen("input.txt","r",stdin); 
#endif

scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
for(i=0;i<=m;++i){
scanf("%d%d",&a[i].l,&a[i].r);
}
int ans = 0;
for(int s=0;s<=m;++s){
if(judge(s))ans++;
}
for(int s=0;s<=m;++s){
for(int t=0;t<s;++t){
if(judge(s,t))ans++;
}
}
printf("%d\n",ans);
}

    return 0;
}

dfs AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<queue>
#include<vector>
#include<set>
using namespace std;
const int T=5000;
#define inf 0x3f3f3f3fL
#define mod 1000000000
typedef long long ll;
typedef unsigned long long ULL;

int n,m;
int cnt;

int he[110],top;
bool vis[110];
struct node
{
int to,next;
node(){}
node(int _to,int _next):to(_to),next(_next){}
}e[110];

inline void Init()
{
memset(he,-1,sizeof he);
top = 1;cnt = 0;
memset(vis,false,sizeof vis);
}

inline void addEdg(int u,int v)
{
//为每条边添加一个编号，即找相同u做起点的边关联起来
e[++top]=node(v,he[u]);he[u] = top;
e[++top]=node(u,he[v]);he[v] = top;
}

void DFS(int x)
{
vis[x] = true;cnt++;
for(int i=he[x];~i;i=e[i].next){
if(vis[e[i].to])continue;
DFS(e[i].to);
}
}

int main()
{
#ifdef zsc 
freopen("input.txt","r",stdin); 
#endif

int i,u0[110],v0[110];
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
for(i=0;i<=m;++i){
scanf("%d%d",&u0[i],&v0[i]);
}
int ans = 0;
for(int s=0;s<=m;++s){
for(int t=s;t<=m;++t){
Init();
for(int k=0;k<=m;++k){
if(s!=k&&t!=k)//s,t可以相同就是包括了删去1，2两条边的情况了
addEdg(u0[k],v0[k]);//建立静态邻接表
}
DFS(1);//判连通性
if(cnt==m)ans++;
}
}
printf("%d\n",ans);
}

    return 0;
}

秒客网

BestCoder Round #73 (div.2)-Rikka with Graph(图的连通性)

Rikka with Graph

题解：

Rikka with Graph

相关文章