【YBT2023寒假Day8 C】圖論題（圖論）（并查集）（線段樹合并）

圖論題

題目連結：YBT2023寒假Day8 C

題目大意

給你一個無向圖，然後你會一直操作直到無法操作，每次找出一個滿足條件的三元組 (a,b,c)，滿足 a<b<c，a,b 與 a,c 之間有邊，b,c 之間沒有邊，然後進行操作把 b,c 連邊。

然後問你最後的圖有多少種用 n 種顔色染色的方案使得每條邊連着的兩個點顔色都不同。

思路

首先考慮如果最後的圖你知道了要怎麼染色。

發現按編号從小到大加入似乎沒有頭豬，考慮反着過來。

發現反着有一個什麼優點呢，就是它可以很好的利用上性質。

那你對于一個點 x x x，它如果跟後面的邊連了 y 1 , y 2 , . . . , y m y_1,y_2,...,y_m y1​,y2​,...,ym​，那根據我們操作的方法，我們會知道 y 1 , y 2 , . . . , y m y_1,y_2,...,y_m y1​,y2​,...,ym​ 之間是兩兩連邊的。

那它們的染色一定就是兩兩不同的，那你 x x x 這個點隻要跟它們都不同就行。

那我們設 d i d_i di​ 為 i i i 點有多少條連向編号比 i i i 大的點，染色方案就是： ∏ i = 1 n ( n − d i ) \prod\limits_{i=1}^n(n-d_i) i=1∏n​(n−di​)

那我們看怎麼求 d i d_i di​ 即可。

考慮我們直接看是否能找到一個 ( x , y ) ( x < y ) (x,y)(x<y) (x,y)(x<y) 有邊的充要條件。

你看到中間的媒介點有 < x , < y <x,<y <x,<y 的條件，那你考慮猜測是不是要存在一條 x x x 到 y y y 的路徑使得路徑上的點除了 x , y x,y x,y 别的編号都 < x <x <x。

考慮證明：

充分性：如果存在這麼一條路徑 x , p 1 , p 2 , . . . , p m , y x,p_1,p_2,...,p_m,y x,p1​,p2​,...,pm​,y，找到這些點中編号最小的點 p k p_k pk​。

那對于 p k − 1 , p k + 1 p_{k-1},p_{k+1} pk−1​,pk+1​ 編号都大于它而且跟它連邊。

那他兩就可以連邊， p k p_k pk​ 就可以不要了。

那最後就隻會剩下 x , y x,y x,y，也就是說明有邊了。

必要性： ( x , y ) (x,y) (x,y) 要麼直接有邊，要麼就是由 ( k , x ) , ( k , y ) ( k < x < y ) (k,x),(k,y)(k<x<y) (k,x),(k,y)(k<x<y) 生成。

那歸納一下， ( k , x ) (k,x) (k,x) 的有邊要麼直接有，要麼再由一個編号 < k <k <k 的生成， ( k , y ) (k,y) (k,y) 同理。

假設由生成的全部遞歸下去，最後會拆成若幹條邊（組成路徑），而這些邊它的編号限制越來越小，也就肯定小于一開始的 x x x。

于是你設 A x A_x Ax​ 集合是原圖中所有跟 x x x 連邊且編号比 x x x 大的。

S i S_i Si​ 則是加邊之後的圖的。

然後 S i S_i Si​ 通過上面的結論，就是 x x x 隻走編号比 x x x 小的點能到達的點的 A x A_x Ax​ 的并集中 > x >x >x 的部分。

那找 > x >x >x 的部分可以用線段樹維護每個的數量。

那至于集合的并，我們可以用并查集維護邊形成的連通塊，然後合并的時候我們可以用線段樹合并來搞。

代碼

#include <bits/stdc++.h>
#define mo 998244353
#define ll long long

namespace quickio
{
	const int bufferSize = 1 << 20; 

	char br[bufferSize], *tailr = br, *headr = br; 
	inline char nextChar()
	{
		if (headr == tailr)
			tailr = (headr = br) + fread(br, 1, bufferSize, stdin); 
		return headr == tailr ? EOF : *headr++; 
	}

	char bw[bufferSize], *tailw = bw; 
	inline void printChar(const char &ch)
	{
		if (tailw == bw + bufferSize)
			fwrite(tailw = bw, 1, bufferSize, stdout); 
		*tailw++ = ch; 
	}
	inline void flush()
	{
		if (tailw != bw)
			fwrite(bw, 1, tailw - bw, stdout); 
	}

	template <class T>
	inline void read(T &x)
	{
		static char ch; 
		while (!isdigit(ch = nextChar())); 
		x = ch - '0'; 
		while (isdigit(ch = nextChar()))
			x = x * 10 + ch - '0'; 
	}

	template <class T>
	inline void putint(T x)
	{
		static char buf[15], *tail = buf; 
		if (!x)
			printChar('0'); 
		else
		{
			for (; x; x /= 10) *++tail = x % 10 + '0'; 
			for (; tail != buf; --tail) printChar(*tail); 
		}
	}
}

using quickio::read; 
using quickio::putint; 
using quickio::printChar;

using namespace std;

const int N = 1e6 + 100;
int n, m, rt[N], fa[N], d[N];
vector <int> G[N];

struct XD_tree {
	int ls[N << 6], rs[N << 6], f[N << 6], tot;
	
	void up(int now) {
		f[now] = f[ls[now]] + f[rs[now]];
	}
	
	void insert(int &now, int l, int r, int pl) {
		if (!now) now = ++tot;
		if (l == r) {
			f[now] = 1; return ;
		}
		int mid = (l + r) >> 1;
		if (pl <= mid) insert(ls[now], l, mid, pl);
			else insert(rs[now], mid + 1, r, pl);
		up(now);
	}
	
	int query(int now, int l, int r, int L, int R) {
		if (!now) return 0;
		if (L <= l && r <= R) return f[now];
		int mid = (l + r) >> 1, re = 0;
		if (L <= mid) re += query(ls[now], l, mid, L, R);
		if (mid < R) re += query(rs[now], mid + 1, r, L, R);
		return re;
	}
	
	int merge(int x1, int x2, int l, int r) {
		if (!x1 || !x2) return x1 + x2;
		if (l == r) {
			f[x1] |= f[x2]; return x1;
		}
		int mid = (l + r) >> 1;
		ls[x1] = merge(ls[x1], ls[x2], l, mid);
		rs[x1] = merge(rs[x1], rs[x2], mid + 1, r);
		up(x1); return x1;
	}
}T;

int find(int now) {
	if (fa[now] == now) return now;
	return fa[now] = find(fa[now]);
}

int main() {
	freopen("graph.in", "r", stdin);
	freopen("graph.out", "w", stdout);
	
//	scanf("%d %d", &n, &m);
	read(n); read(m);
	for (int i = 1; i <= m; i++) {
//		int x, y; scanf("%d %d", &x, &y);
		int x, y; read(x); read(y);
		if (x < y) swap(x, y); G[x].push_back(y);
		T.insert(rt[y], 1, n, x);
	}
	
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < G[i].size(); j++) {
			int x = G[i][j];
			int X = find(i), Y = find(x);
			if (X == Y) continue;
			rt[Y] = T.merge(rt[Y], rt[X], 1, n); fa[X] = Y;
		}
		d[i] = T.query(rt[find(i)], 1, n, i + 1, n);
	}
	
	ll ans = 1;
	for (int i = 1; i <= n; i++)
		ans = ans * (n - d[i]) % mo;
	putint((int)ans);
//	printf("%lld", ans);
	
	quickio::flush();
	return 0;
}