【ybt高效進階 21160】仙人之環（貪心）（Tarjan）（無向圖仙人掌）

仙人之環

題目連結：ybt高效進階 21160

題目大意

給你一個無向圖仙人掌森林，然後讓你選 k 條邊删掉，問你最多能形成多少個連通塊。

思路

首先我們要發現這是個仙人掌森林。

然後你發現如果不是在環上的邊，你删了連通塊就會多 1 1 1，否則就不會多。

那如果你删一個一個環的一條邊，環剩下的邊就變成不是在環上的邊了。

（也就是說第一個不能加，剩下的邊都能加）

那不難想到先上不是環上的邊，再删環上的。

那删環上的也要有一個順序，不難貪心想到肯定是從大環開始删。

那接着問題就是找環了，由于是仙人掌，我們可以用 Tarjan 來搞。

就找出每個環，但由于這個是無向圖，我們判斷是否從走來的邊走回去時要用邊來判斷，不要用點。

然後就好啦。

代碼

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

struct node {
	int to, nxt;
}e[4000003];
int n, m, k, x, y, ans;
int KK, le[1000001], bnl;
int dfn[1000001], bn[1000001];
int re, cn[1000001];
int low[1000001], sta[1000001], tmp;
bool br[4000003], in[1000001];
char c;

int read() {
	re = 0;
	c = getchar();
	while (c < '0' || c > '9') {
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		re = (re << 3) + (re << 1) + c - '0';
		c = getchar();
	}
	return re;
}

void add(int x, int y) {
	e[++KK] = (node){y, le[x]}; le[x] = KK;
	e[++KK] = (node){x, le[y]}; le[y] = KK;
}

void work(int now, int edge) {
	dfn[now] = low[now] = ++tmp;
	for (int i = le[now]; i; i = e[i].nxt)
		if (i != (edge ^ 1)) {//要判的是邊不是點
			if (!dfn[e[i].to]) {
				sta[++sta[0]] = i;
				work(e[i].to, i);
				low[now] = min(low[now], low[e[i].to]);
				if (low[e[i].to] >= dfn[now]) {//有環
					bn[0]++;
					while (sta[0] && sta[sta[0]] != i) {
						sta[0]--; bn[bn[0]]++;
					}
					bn[bn[0]]++;
					sta[0]--;
					if (bn[bn[0]] == 1) bn[bn[0]--] = 0;
						else bnl += bn[bn[0]];
				}
			}
			else if (dfn[e[i].to] < low[now]) {
				sta[++sta[0]] = i;
				low[now] = min(low[now], dfn[e[i].to]);
			}
		}
}

int tong[2000001];

void Sort() {//桶排
	for (int i = 1; i <= bn[0]; i++)
		tong[bn[i]]++;
	for (int i = 2; i <= m; i++)
		tong[i] += tong[i - 1];
	for (int i = bn[0]; i >= 1; i--)
		cn[tong[bn[i]]--] = bn[i];
}

int main() {
//	freopen("c.in", "r", stdin);
//	freopen("c.out", "w", stdout);
	
	n = read(); m = read(); k = read();
	KK = 1;
	for (int i = 1; i <= m; i++) {
		x = read(); y = read();
		add(x, y);
	}
	
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) {
			work(i, 0);
			ans++;
		}
	}
	
	ans += min(k, m - bnl);
	k -= min(k, m - bnl);
	
	Sort();//貪心，先拆打的環
	
	int noww = bn[0];
	while (k && noww) {
		ans += min(k, cn[noww]) - 1;
		k -= min(k, cn[noww]);
		noww--;
	}
	
	printf("%d", ans);
	
	return 0;
}