abc260F - Find 4-cycle

F - Find 4-cycle

显然就是在一个集合中枚举两个点，然后看在另一个集合中是否存在两个点与这个集合中的两个点都相连。

假设x是v1中的一个点，设它的两条出边是(x,a),(x,b)，那么记录下f[a][b]=x，根据鸽巢原理，这样做是n^2的

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<unordered_map>
#include<bitset>
#include<vector>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int N = 3e5+5;
const ll inf = 1ll << 60;
const ll mo = 998244353;
int s,t,m,x,y;
int f[3005][3005];
vector<int> v[N];
void R(int &x){
	char ch;
	int t=0;
	for (ch=getchar();!('0'<=ch && ch<='9');ch=getchar());
	for (;('0'<=ch&&ch<='9');ch=getchar()) t=t*10+ch-'0';
	x=t;
}
int main()
{

//	freopen("data.in","r",stdin);
	
	R(s); R(t); R(m);
	fo(i,1,m){
		R(x); R(y); y-=s;
		v[x].push_back(y); 
	}
	
	fo(i,1,s) {
		for (auto x:v[i]) {
			for (auto y:v[i]) {
				if (x==y) continue;
				
				if (f[x][y]) {
					printf("%d %d %d %d",i,x+s,f[x][y],y+s);
					return 0;
				}
				
				f[x][y]=i;
			}
		}
	}

	puts("-1");

	return 0;
}