题解 | #分组#

D题
因为细节错误，最后一分钟才A出来。。。。。。。

首先，我们有一个很明显的贪心。
就是，我们从左到右去枚举边的话，肯定是尽量囊括边 到濒临阈值的情况下

即，我们从最左端一直向右取边，取到极限，算作一组
然后以当前位置为最左端，向右取边取到极限，算作一组
以此类推。

但是我们是无法这样做的，因为我们无法做到动态的查询强连通分量

那么二分可不可以呢？
首先我们以最左端编号1开始二分，找到他可以取到的最右端的编号l2
然后再次二分。。。。
每次二分都使用一次tajan算法验证一遍

但是这样行不行呢？
没试，但是预计会T 我们可以大致感觉到这个复杂度是有点高的

这时，我看了下数据

然后我们可以意识到一个重要的结论：
如果我这个图中只有n个点，那么这个图的重量一定是<=n^2的！！！！
即，我这些点连成了一个强连通

这个结论扩展到边也差不多
如果这个图有m个边,n个点。那么这个图的重量一定是<=m^2 + n-m ！！！！！
即，我m条边构造了一个有m个点的强连通分量，然后剩余n-m个孤立的点！！

一句这个结论我们可以做到什么？
这说明了，我们在一开始就可以按照结论，将整个边序列分成大致 个区间！！！！

然后我们需要考虑的就变成了：
从最左边开始，一个一个地合并区间！
能合并就合并，无法合并就取最右(依照我们之前的贪心策略，我们要尽量包含多的边取到上限！)

而这里，如何找到最右边的那个上限，我们就可以使用二分了！

当然，为了不T我们还需要，稍微修改一下tarjan，中遍历点的情况
即：我们只要保留我们所选区间的点即可。
具体实现见代码：

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
using namespace std;
typedef long long ll;
const int max_n = 1e6+100;
int n,m;
ll k;
int es[max_n][2];
vector<int> V;
struct edge
{
    int to,next;
}E[max_n<<1];
int head[max_n];
int cnt=1;
void add(int from,int to)
{
    E[cnt].to=to;
    E[cnt].next=head[from];
    head[from]=cnt++;
}

int dfn[max_n],low[max_n];
stack<int> st;
int colour=0;
int color[max_n];
int sz[max_n<<1];
int tot=0;
void tarjan(int u) {
    dfn[u] = low[u] = ++tot;
    st.push(u);
    for (int i = head[u];i;i = E[i].next)
    {
        int v = E[i].to;
        if (!dfn[v]) 
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (color[v] == 0)low[u] = min(low[u], dfn[v]);
    }
    if (low[u] != dfn[u])return;

    colour++;
    while (st.top() != u) 
    {
        color[st.top()] = colour;
        st.pop();
        sz[colour]++;
    }
    color[st.top()] = colour;
    st.pop();
    sz[colour]++;
}


int que[max_n];
int h=0;
int cct=0;
int vis[max_n];
bool check(int l,int r)
{
    ++cct;
    int nodes = 0;
    h=0;
    for (int i=l;i<=r;++i)
    {
        que[++h]=es[i][0];
        que[++h]=es[i][1];
        if (vis[es[i][0]]!=cct)
        {
            vis[es[i][0]]=cct;
            ++nodes;
        }
        if (vis[es[i][1]]!=cct)
        {
            vis[es[i][1]]=cct;
            ++nodes;
        }
    }
    nodes = n-nodes;
    cnt=1;
    for (int i=1;i<=h;++i)head[que[i]]=dfn[que[i]]=low[que[i]]=color[que[i]]=0;
    for (int i=l;i<=r;++i)add(es[i][0],es[i][1]);

    ll ans = 0;
    tot=0;
    colour=0;
    for (int i=0;i<=h;++i)sz[i]=0;
    while (!st.empty())st.pop();

    for (int i=1;i<=h;++i)
    {
        if (dfn[que[i]])continue;
        tarjan(que[i]);
    }

    for (int i=1;i<=colour;++i)
        ans+= (ll)sz[i]*(ll)sz[i];

    return ans+nodes<=k;
}

int Solve(int cur,int l,int r)
{
//    cout<<cur<<" "<<l<<" "<<r<<endl;
    --r;
    if (check(cur,r))return cur;
    int ans=l-1;
    int lft = l-1,rgt=r;
    while (lft<=rgt)
    {
        int mid = (lft+rgt)>>1;
        if (check(cur,mid))
        {
            lft = mid+1;
            ans = mid;
        }
        else rgt =mid-1;
    }
    ++ans;
    if (ans==r+1)return cur;
    else return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m>>k;
    for (int i=1;i<=m;++i)cin>>es[i][0]>>es[i][1];
    V.push_back(1);
    ll lim = sqrt(k);
    while (lim*lim+n-lim>k)--lim;
    for (int i=2;i<=m;++i)
        if (i-V.back()==lim)
            V.push_back(i);

    if (V.size()==1)
    {
        cout<<1<<endl;
        return 0;
    }

    else if (V.size()==2)
    {
        if (check(1,m))cout<<1<<endl;
        else cout<<2<<endl;
        return 0;
    }

    int ans = 1;
    V.push_back(m+1);
    int cur = 1;

    for (int i=1;i<V.size()-1;++i)
    {
        int pre = cur;
        cur = Solve(cur,V[i],V[i+1]);
        if (cur!=pre)++ans;
    }
    cout<<ans<<endl;
}