LYDSY 3444
题目大意
暂无
题目解法
暂无
RTFC
#include <cctype>
#include <cstdio>
#include <map>
typedef long long int64;
const int64 mod = 989381;
const int maxn = 500010;
inline void readInt(int &x)
{
int ch = x = 0;
bool F = false;
for (; !isdigit(ch = getchar()); F = (ch == '-'))
;
for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
F && (x = -x);
}
int fa[maxn], cnt[maxn], deg[maxn], head[maxn], to[maxn << 1], next[maxn << 1], idx, n, m, num;
bool vis[maxn];
std::map<int, bool> M[maxn];
int Find(int x) { return x == fa[x] ? x : fa[x] = Find(fa[x]); }
void link(int x, int y)
{
int fx = Find(x), fy = Find(y);
if (fx != fy)
{
fa[fx] = fy;
cnt[fy] += cnt[fx];
cnt[fx] = 0;
}
}
inline void addEdge(int x, int y)
{
idx++;
to[idx] = y;
next[idx] = head[x];
head[x] = idx;
}
int fast_pow(int64 base, int pow)
{
int ans = 1;
for (; pow; base = (base * base) % mod, pow >>= 1)
if (pow & 1)
ans = (ans * base) % mod;
return ans;
}
void dfs(int id, int f)
{
num++;
vis[id] = true;
if (num > n) return;
for (int cur = head[id]; cur; cur = next[cur])
if (to[cur] != f)
dfs(to[cur], id);
}
bool check()
{
for (int i = 1; i <= n; i++)
if (deg[i] > 2) return false;
for (int i = 1; i <= n; i++)
if (!vis[i])
if (deg[i] == 1)
dfs(i, 0);
else if (deg[i] == 0)
vis[i] = true, num++;
return num == n;
}
int main()
{
for (int i = 0; i < maxn; i++) fa[i] = i, cnt[i] = 1;
readInt(n), readInt(m);
for (int i = 0, x, y; i < m; i++)
{
readInt(x), readInt(y);
if (M[x][y] || M[y][x]) continue;
addEdge(x, y), addEdge(y, x);
deg[x]++, deg[y]++;
link(x, y);
M[x][y] = M[y][x] = true;
}
int64 ans = 0;
if (check())
{
ans = 1;
int l = 0, p = 0;
for (int i = 1; i <= n; i++)
if (fa[i] == i)
(cnt[i] > 1 ? l : p)++;
for (int i = 1; i <= l + p; i++) ans = (ans * i) % mod;
ans = (ans * fast_pow(2, l)) % mod;
}
printf("%lld", ans);
return 0;
}