CF#318-B - Bear and Three Musketeers-暴力寻找三元环_如何找三元环

题意是给你n个点m条边

求出一个三元环（与a相连的边包括b,c）、（与b相连的边包括a,c）（与c相连的边包括a,b）

n,m都是1-4000

一开始觉得暴力枚举复杂度肯定过不了。

随手打了一发交了一次居然才62ms......后来再算算 的确数据规模有点小，直接暴力就可以了

因为需要这个操作 与b相连的所有边中寻找是否存在c，所以直接用set构建邻接表了，查找就可以logn了

暴力枚举每一条度数大于2的边，对所有与它相连的边，查询（b中是否有c，c中是否有b）、如果为真，则abc为三元环

然后一直更新 a.size+b.size+c.size-6  （减6是因为 recognition 是不包括环内的队友的）

复杂度是  o(n)-o(n^2)  

最糟糕的情况是  所有边连接在一个点上  

 
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define inf 2147483647
set<int> qq[4005];
set<int> ::iterator it,tmp,t1,t2;
int main()
{
	
	int n,i,j,tt,m;
	scanf("%d%d",&n,&m);
 
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&tt,&j);
		qq[tt].insert(j);
		qq[j].insert(tt);
	}
	int maxx=inf;
for (i=1;i<=n;i++)
{
	if (qq[i].size()<2) continue;
	for (it=qq[i].begin();it!=qq[i].end();it++)
	{
		tmp=it;
		tmp++;
		//printf("%d %d--\n",*it,*tmp);
		for (;tmp!=qq[i].end();tmp++)
		{
			if (   qq[(*it)].count(*tmp)&&qq[(*tmp)].count(*it)  )
			{
				int ans=qq[*it].size()+qq[*tmp].size()+qq[i].size();
				if (ans-6<maxx)
					maxx=ans-6;
			}
		}
	}
 
}
if (maxx==inf)
printf("-1\n");
else
printf("%d\n",maxx);
 
	return 0;
	
}