列表

详情

NC219030. 统计个数

描述

给出一张N个点M条边的图，假设图中有三个节点分别为a,b,c，若点a和点b之间有边并且b和c之间有边的话，我们就称(a,b,c)为一条线，同时视(c,b,a)和(a,b,c)为同一条线，而对于其他的组合则认为是和(a,b,c)不同的线。

如果(a,b,c)是一条线并且点a和点c之间也有边的话，我们称(a,b,c)构成一个三角，同理我们视由这三个点组成的三角为同一个三角，即(a, b, c)、(a, c, b)、(b, a, c)、(b, c, a)、(c, a, b)、(c, b, a)只能被算一次

请分别统计给定的图中，三角和线的数量

输入描述

第一行一个正整数,代表测试数据的组数

第二行给出一个正整数，代表点数，图的节点编号为

第三行给出一个正整数，代表图中的边数

接下来M行每行给出两个正整数a_i,b_i，代表a_i,b_i之间有边相连

题目保证图中至少存在一条线并且不存在重边和自环

输出描述

对于每组数据请输出一个分数代表三角和线数量的比，格式为，(其中p为三倍的三角的数量，q为线的数量)

请输出最简分数，若，则输出。

示例1

输入: 

3
5
7
1 2
2 3
1 3
3 4
2 4
4 5
1 5
3
3
1 2
3 1
3 2
4
3
1 2
2 3
3 4

输出: 

6/13
1/1
0/1

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 89ms, 内存消耗: 864K, 提交时间: 2021-05-12 23:22:36 

#include<bits/stdc++.h>

using namespace std;

void init(){
	int n,m;
	cin>>n>>m;
	int a[210][210];
	memset(a,0,sizeof a);
	while(m--){
		int x,y;
		cin>>x>>y;
		if(x!=y)
		a[x][y]=a[y][x]=1;
	}
	int suma=0,sumb=0;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	for(int k=1;k<=n;k++){
		if(a[i][j]&&a[j][k]&&i!=k){
			suma++;
			if(a[i][k])
			sumb++;
		}
	}
	if(sumb==0)
	cout<<"0/1\n";
	else{
		int x=__gcd(suma,sumb);
		cout<<sumb/x<<"/"<<suma/x<<endl;
	}
}

int main(){
	int t;
	cin>>t;
	while(t--)
	init();
}

上一题

© 2024 nowcoder.com