给出一个nn个点,mm 条边的无向图,求由 kk 条边构成的联通子图的个数,对109+710^9 + 7取模

n105,m2105,k4n\le10^5,m\le2*10^5,k\le4

FZOJ 191

Pre-Algorithm

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

Three-Membered Ring

19-3-1-1

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

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

然后考虑一个暴力做法:

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

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

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

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

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

Four-Membered Ring

19-3-1-2

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

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

在三元环计数中valjval_jvalkval_k的大小关系可以任意,而四元环中必须要满足valj<valkval_j < val_k,所以不行

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

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

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

Solution

大力枚举 + 分类讨论

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

下面讨论k=4k=45种情况:

19-3-1-3

  1. 菊花:

    枚举点ii,用度数算一下

  2. 一条边,一边连两个点,另一边连一个点:

    枚举边ii,用度数算一下。此时cc可能与aabb重合形成情况3,所以要减掉22情况3

  3. 三元环,连一个点:

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

  4. 链:

    枚举点ii,枚举与ii相邻的点yyaa为当前的yycc为之前枚举过的yy,然后利用度数计算贡献,此时多算的情况:

    • bbdd重合形成情况5
    • bbcc重合且aadd重合,形成情况3
    • aacc重合且bbdd重合,形成三元环

    总共要减去22情况522情况311三元环

  5. 四元环:

    之前讲过了

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
#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;
}