「FJWC2019」子图 - 分类讨论 + 枚举 + 暴力

给出一个$n$个点，$m$ 条边的无向图，求由 $k$ 条边构成的联通子图的个数，对$10^9 + 7$取模

$n\le10^5,m\le2*10^5,k\le4$

Links

FZOJ 191

Pre-Algorithm

你得会在$O(m\sqrt m)$的复杂度内进行三元环和四元环计数

Three-Membered Ring

首先把无向图转成有向图，由度数小的向度数大的连边，度数相同就由编号小的向编号大的

那么这样连出来的一定是一个有向无环图

然后考虑一个暴力做法：

• 先枚举点$i$， 把所有$i$连向的点标记为$i$
• 枚举$i$连向的点$j$
• 枚举$j$连向的点$k$，若$k$被标记为$i$，则存在一个三元环$(i, j, k)$

因为无向图被我们转化成了dag，所以每个三元环只会在度数最小的点处被统计，不会算重

复杂度的话，显然等于所有被指向点的出度的和

而每个点的出度是不会大于$\sqrt m$（若存在一个点出度大于$\sqrt m$，那么它所有出边指向的点的度数都要大于$\sqrt m$，边的总数就会大于$m$）

所以复杂度为$O(m\sqrt m)$

Four-Membered Ring

四元环的计数与三元环类似，先枚举点$i$，然后枚举连向的点$j$，再枚举$j$连向的点$k$。记录一个$cnt$数组，答案每次加上$cnt[k]$，然后++cnt[k]。但是在这里不能转化成有向图

因为如果建成有向图，设$val$表示一个点按$(deg, id)$排序的值，那么有$val_i < val_j, val_i < val_k$，但是我们并不确定$val_j$和$val_k$的大小关系

在三元环计数中$val_j$和$val_k$的大小关系可以任意，而四元环中必须要满足$val_j < val_k$，所以不行

考虑一个类似的做法，将所有点重标号，并且把每个点连出的边按照所连出点的$val$值排序

在枚举点的过程中，始终保证$val_i < val_j,val_i < val_k$，如果不满足就立刻break

与三元环证明方法类似，这个做法也可以被证明是$O(m\sqrt m)$的

Solution

大力枚举 + 分类讨论

$k=3$时，讨论一下菊花、链、三元环的情况即可，其中算链的时候会多算三次三元环的情况，注意要减去

下面讨论$k=4$的5种情况：

1. 菊花：

   枚举点$i$，用度数算一下

2. 一条边，一边连两个点，另一边连一个点：

   枚举边$i$，用度数算一下。此时$c$可能与$a$或$b$重合形成情况3，所以要减掉$2$次情况3

3. 三元环，连一个点：

   枚举三元环，用三元环上点的度数算一下

4. 链：

   枚举点$i$，枚举与$i$相邻的点$y$，$a$为当前的$y$，$c$为之前枚举过的$y$，然后利用度数计算贡献，此时多算的情况：

   • $b$和$d$重合形成情况5
   • $b$和$c$重合且$a$和$d$重合，形成情况3
   • $a$和$d$重合且$b$和$c$重合，形成三元环

   总共要减去$2$次情况5，$2$次情况3，$1$次三元环

5. 四元环：

   之前讲过了

时间复杂度$O(m\sqrt m)$，代码、细节复杂度$O(\infty)$

Code

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100, Maxm = Maxn << 1;
const int Mod = 1e9 + 7;

namespace MATH
{
	int fac[Maxm], ifac[Maxm];

	inline void Add (int &a, int b) { a += b; if (a >= Mod) a -= Mod; }

	inline int Pow (int a, int b)
	{
		int ans = 1;
		for (int i = b; i; i >>= 1, a = (LL)a * a % Mod) if (i & 1) ans = (LL)ans * a % Mod;
		return ans;
	}

	inline int Binom (int n, int m) { if (n < m) return 0; return (LL)fac[n] * ifac[m] % Mod * ifac[n - m] % Mod; }

	inline void math_init (int maxn)
	{
		fac[0] = 1;
		for (int i = 1; i <= maxn; ++i) fac[i] = (LL)fac[i - 1] * i % Mod;
		ifac[maxn] = Pow(fac[maxn], Mod - 2);
		for (int i = maxn - 1; i >= 0; --i) ifac[i] = (LL)ifac[i + 1] * (i + 1) % Mod;
	}
}

using namespace MATH;

int N, M, K;
int deg[Maxn];
vector <int> G[Maxn];
pii E[Maxm];

inline int cmp (int x, int y)
{
	if (deg[x] == deg[y]) return x < y;
	return deg[x] < deg[y];
}

namespace Three
{
	int Vis[Maxn];

	inline int calc (int x)
	{
		int ans = 0;

		for (int y : G[x]) Vis[y] = x;
		for (int y : G[x]) for (int z : G[y]) if (Vis[z] == x) Add (ans, 1); 

		return ans;
	}

	inline int solve ()
	{
		int ans = 0;

		// 1. Star
		for (int i = 1; i <= N; ++i) Add (ans, Binom (deg[i], 3));

		// 2. Chain
		for (int i = 1; i <= M; ++i) Add (ans, (LL)(deg[E[i].x] - 1) * (deg[E[i].y] - 1) % Mod);

		// 3. Ring
		for (int i = 1; i <= N; ++i) Add (ans, Mod - 2ll * calc (i) % Mod);

		return ans;
	}
}

namespace Four
{
	int Vis[Maxn];

	inline int calc (int x)
	{
		int ans = 0;
		for (int y : G[x]) Vis[y] = x;

		for (int y : G[x])
		{
			for (int z : G[y])
			{
				if (Vis[z] != x) continue;

				Add (ans, 1);
				Add (ans, ((deg[x] - 2) + (deg[y] - 2) + (deg[z] - 2)) % Mod);
			}
		}

		return ans;
	}

	inline int calc_chain (int x)
	{
		int ans = 0, sum = 0;
		for (int y : G[x])
		{
			Add (ans, (LL)sum * (deg[y] - 1));
			sum += deg[y] - 1;
		}
		return ans;
	}

	int cnt[Maxn];

	inline int calc_ring (int x)
	{
		int ans = 0;
		vector <int> Save; Save.clear();

		for (int y : G[x])
		{
			if (!cmp(y, x)) break;
			for (int z : G[y])
			{
				if (!cmp(z, x)) break;
				Add (ans, cnt[z]), ++cnt[z], Save.pb(z);
			}
		}

		for (int x : Save) cnt[x] = 0;

		return ans;
	}

	inline int solve ()
	{
		int ans = 0;

		// 1. Star
		for (int i = 1; i <= N; ++i) Add (ans, Binom(deg[i], 4));

		// 2. Edge with 2 points on one side, and 1 point on the other side
		for (int i = 1; i <= M; ++i)
		{
			int x = deg[E[i].x], y = deg[E[i].y];
			Add (ans, (LL)Binom (x - 1, 2) * (y - 1) % Mod);
			Add (ans, (LL)Binom (y - 1, 2) * (x - 1) % Mod);
		}

		// 3. Three-membered ring with 1 point
		for (int i = 1; i <= N; ++i) Add (ans, Mod - 3ll * calc (i));

		// Add undirected edge
		for (int i = 1; i <= M; ++i) G[E[i].y].pb(E[i].x);

		//4. Chain
		for (int i = 1; i <= N; ++i) Add (ans, calc_chain (i));

		//5. Four-membered ring
		static int Rank[Maxn];
		for (int i = 1; i <= N; ++i) Rank[i] = i, sort(G[i].begin(), G[i].end(), cmp);
		sort(Rank + 1, Rank + N + 1, cmp);
		for (int i = 1; i <= N; ++i) Add (ans, (LL)(Mod - 3) * calc_ring (Rank[i]) % Mod);

		return ans;
	}
}

inline void Solve ()
{
	int ans = 0;

	if (K == 1) ans = M;
	else if (K == 2) for (int i = 1; i <= N; ++i) Add (ans, Binom (deg[i], 2));
	else if (K == 3) ans = Three :: solve ();
	else ans = Four :: solve ();
	
	cout << ans << endl;
}

inline void Input ()
{
	N = read<int>(), M = read<int>(), K = read<int>();

	for (int i = 1; i <= M; ++i) E[i].x = read<int>(), E[i].y = read<int>(), ++deg[E[i].x], ++deg[E[i].y];

	for (int i = 1; i <= M; ++i)
	{
		if (!cmp(E[i].x, E[i].y)) swap(E[i].x, E[i].y);
		G[E[i].x].pb(E[i].y);
	}
}

int main()
{

	freopen("subgraph.in", "r", stdin);
	freopen("subgraph.out", "w", stdout);

	math_init(2e5);
	Input ();
	Solve ();

	return 0;
}