C++(clang++11) 解法, 执行用时: 441ms, 内存消耗: 14848K, 提交时间: 2021-04-11 15:51:18

#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int maxm=1e6+5;
int n,m;
ll q,cnt;
ll tot;
int x[maxm],y[maxm],ex[maxn],dfn[maxn],low[maxn];
vector<int> v,g[maxn];
stack<int> st;
void tarjan(int x){
	low[x]=dfn[x]=++cnt;
	st.push(x);ex[x]=1;
	for(int v:g[x]){
		if(!dfn[v]){
			tarjan(v);
			low[x]=min(low[x],low[v]);	
		}else if(ex[v])
			low[x]=min(low[x],low[v]);
	} 
	if(low[x]==dfn[x]){
		int sz=1;
		while(st.top()!=x){
			ex[st.top()]=0;
			st.pop();
			++sz;
		}
		st.pop();
		tot+=1ll*sz*sz;
	}
}
bool check(int l,int r){
	v.clear();
	for(int i=l;i<=r;++i)
		v.push_back(x[i]),g[x[i]].push_back(y[i]),dfn[x[i]]=dfn[y[i]]=0;
	int m=v.size();
	tot=n;
	for(int i=0;i<m;++i)
		if(!dfn[v[i]]){
			cnt=0,tarjan(v[i]);tot-=cnt;
		}
	for(int i=l;i<=r;++i)
		g[x[i]].clear();
	return tot<=q;
}
int main(){
	scanf("%d%d%lld",&n,&m,&q);
	for(int i=1;i<=m;++i)
		scanf("%d%d",&x[i],&y[i]);
	int ans=0;
	for(int r,L=1;L<=m;L=r+1){
		int k=0;
		while(check(L,L+(1<<k)-1)){
			if(L+(1<<k)-1>m)break;
			++k;
		}
		int l=L+(1<<(k-1))-1;r=min(m,L+(1<<k)-1);
		while(l<r){
			int mid=(l+r+1)>>1;
			if(check(L,mid))
				l=mid;
			else
				r=mid-1;
		}
		++ans; 
	}
	printf("%d\n",ans);
	return 0;
}