HDU 6184&& 2017广西邀请赛 Counting Stars(三元环计数)
CountingStars
Time Limit: 4000/2000 MS(Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 309 Accepted Submission(s):82
Problem Description
Little A is an astronomy lover, and he hasfound that the sky was so beautiful!
So he is counting stars now!
There are n stars in the sky, and little A has connected them by mnon-directional edges.
It is guranteed that no edges connect one star with itself, and every two edgesconnect different pairs of stars.
Now little A wants to know that how many different "A-Structure"s arethere in the sky, can you help him?
An "A-structure" can be seen as a non-directional subgraph G, with aset of four nodes V and a set of five edges E.
If V=(A,B,C,D) and E=(AB,BC,CD,DA,AC), we call G as an "A-structure".
It is defined that "A-structure" G1=V1+E1 and G2=V2+E2 are same only in the condition that V1=V2 and E1=E2.
Input
There are no more than 300 test cases.
For each test case, there are 2 positive integers n and m in the first line.
2≤n≤105, 1≤m≤min(2×105,n(n−1)2)
And then m lines follow, in each line there are two positive integers u and v,describing that this edge connects node u and node v.
1≤u,v≤n
∑n≤3×105,∑m≤6×105
Output
For each test case, just output oneinteger--the number of different "A-structure"s in one line.
Sample Input
4 5
1 2
2 3
3 4
4 1
1 3
4 6
1 2
2 3
3 4
4 1
1 3
2 4
Sample Output
1
6
题目意思是说，在一个给定的无向图中，找"A-structure"的个数。
"A-structure"这个题目有解释，V=(A,B,C,D) and E=(AB,BC,CD,DA,AC)
这样的一个点集和边集就是符合条件的。
开始没太看懂题目，僵化地认为必须是一个一个由四个点组成的环+一条对角线
这样怎么也解释不了第二个样例。
只好转头在看一遍题目。
其实题目叫我们找的是两个三元环，这两个三元环共用一条边。
比如说V=(A,B,C,D) and E=(AB,BC,CD,DA,AC)这个里面是
三元环ABC和三元环ADC共用了AC。
样例二给的是一个完全图，一共有六条边。这六条边，每一条边都可以作为像上面AC一样的共边。，都能找到两个三元环。
这样，这道题目其实就用简单的方法就可以过。
我们每次枚举一条边，看它是否能作为共边，如果它是，那数有多少个点能够和这条边构成三元环。最后的答案就是C（cnt，2），（这符合条件的点中任选两个都符合A-structure）
比如说样例二，开始判断AB是否满足条件。发现它满足，C和D都可以与AB边构成三元环，所以以AB为共边的A-structure有C(2.2)个，也就是一个，其他5条边也是类似。
这样的确实能够解决问题，但是我们估计一下算法复杂度，发现时间不够。
所以我们需要优化一下。
我们有两种方法来枚举（具体看代码）
一种是枚举X，一种是枚举Y，
为了降低算法复杂度，我们需要根据两个点集的大小来选择哪种方式
这时候，我们可以选择以Sqrt（m）作为为一个分界点，具体可看代码
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<math.h>
#include<string>
#include<stdio.h>
#include<map>
#include<vector>
#include<deque>
#include<algorithm>
#define maxn 100005
using namespace std;
map<pair<int,int>,int> maps;
vector<int> p[maxn];
int outdeg[maxn],link[maxn],vis[maxn];
int n,m;
long long ans;
void init()
{
ans=0;
maps.clear();
memset(outdeg,0,sizeof (outdeg));
memset(link,0,sizeof (link));
memset(vis,0,sizeof (vis));
for(int i=1;i<=n;i++)
p[i].clear();
}
int main()
{
int i,j,k;
int x,y,z;
int t,a,b,c;
long long sum;
pair<int,int> tmp1,tmp2;
while(scanf("%d%d",&n,&m)!=EOF)
{
init();//清空
t=sqrt(m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
p[a].push_back(b);//存储双向边
p[b].push_back(a);
outdeg[a]++; outdeg[b]++;//统计每个点的度数
tmp1=make_pair(a,b);//把边加入Map里面
tmp2=make_pair(b,a);//方便后面查找
maps[tmp1]=1;//用set，Hash都可以，只要后面能找到边即可
maps[tmp2]=1;
}
for(i=1;i<=n;i++)//开始枚举
{
x=i;
vis[x]=1;
for(j=0;j<p[x].size();j++)
{
y=p[x][j];
link[y]=x;//与之相连的边标记出来
}
for(j=0;j<p[x].size();j++)
{
sum=0;
y=p[x][j];//这里比较重要，此时我们选择的边是XY
if(vis[y])//每个点枚举一次
continue;
if(outdeg[y]<=t)//分界点
{
for(k=0;k<p[y].size();k++)
{
z=p[y][k];//此时选择YZ边
if(link[z]==x)//如果XZ相连
sum++;//可构成三元环，计数
}
}
else
{
for(k=0;k<p[x].size();k++)
{
z=p[x][k];//此时XZ相连
pair<int,int> tmp=make_pair(z,y);
if(maps[tmp]!=0)//如果ZY相连
sum++;//可构成三元环，计数
}
}
ans+=(sum*(sum-1))/2;//最后答案是C(cnt,2);
}
}
printf("%lld\n",ans);
}
return 0;
}
查看21道真题和解析
