2 seconds

256 megabytes

standard input

standard output

#include <bits/stdc++.h>

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define all(a) (a).begin(), (a).end()

#define fillchar(a, x) memset(a, x, sizeof(a))

#define huan printf("\n");

#define debug(a,b) cout<<a<<" "<<b<<" ";

using namespace std;

const int maxn=2e5+;

typedef long long ll;

vector<int> g[maxn];

map<pair<int,int>,int> ma;

int a[maxn];

int b[maxn];

int main()

{

    int n;

    cin>>n;

    for(int i=;i<n-;i++)

    {

        int u,v;

        cin>>u>>v;

        g[u].pb(v);

        g[v].pb(u);

        ma[mp(u,v)]=;

        ma[mp(v,u)]=;

    }

    for(int i=;i<=n;i++)

        cin>>a[i];

    if(a[]!=)

    {

        cout<<"No"<<endl;

        return ;

    }

    int flag=,before=;

    for(int i=;i<n;i++)

    {

        int num=;

        for(int j=;j<g[a[i]].size();j++)

            if(b[g[a[i]][j]]==)num++;

        //cout<<i<<" "<<num<<endl;

        for(int j=;j<num;j++)

        {

            if(before+j+>n)

                break;

           // cout<<a[i+j+1]<<" j"<<j<<endl;

            if(ma[mp(a[i],a[before+j+])]!=)

            {

                flag=;

                break;

            }

            //else

              //  b[a[i+j+1]]=1;

        }

        before=before+num;

        //cout<<a[i]<<" "<<flag<<endl;

        b[a[i]]=;

        if(flag==)

            break;

    }

    if(flag)

        cout<<"Yes"<<endl;

    else

        cout<<"No"<<endl;

}

There are nn persons who initially don't know each other. On each morning, two of them, who were not friends before, become friends.

We want to plan a trip for every evening of mm days. On each trip, you have to select a group of people that will go on the trip. For every person, one of the following should hold:

• Either this person does not go on the trip,
• Or at least kk of his friends also go on the trip.

Note that the friendship is not transitive. That is, if aa and bb are friends and bb and cc are friends, it does not necessarily imply that aa and cc are friends.

For each day, find the maximum number of people that can go on the trip on that day.

The first line contains three integers nn, mm, and kk (2≤n≤2⋅105,1≤m≤2⋅1052≤n≤2⋅105,1≤m≤2⋅105, 1≤k<n1≤k<n) — the number of people, the number of days and the number of friends each person on the trip should have in the group.

The ii-th (1≤i≤m1≤i≤m) of the next mm lines contains two integers xx and yy (1≤x,y≤n1≤x,y≤n, x≠yx≠y), meaning that persons xx and yy become friends on the morning of day ii. It is guaranteed that xx and yy were not friends before.

Print exactly mm lines, where the ii-th of them (1≤i≤m1≤i≤m) contains the maximum number of people that can go on the trip on the evening of the day ii.

In the first example,

• 1,2,31,2,3 can go on day 33 and 44.

In the second example,

• 2,4,52,4,5 can go on day 44 and 55.
• 1,2,4,51,2,4,5 can go on day 66 and 77.
• 1,2,3,4,51,2,3,4,5 can go on day 88.

In the third example,

• 1,2,51,2,5 can go on day 55.
• 1,2,3,51,2,3,5 can go on day 66 and 77.

解析 我们离线处理这个问题，先把每个点的入度和编号用pair保存起来 扔到set里面 ，每次把度数小于k的点删掉，与它相邻的点 j 度数减1 。把原来在set里的pair<du[j],j>删掉，再插入新的点

直到 set里的点的度数都大于k。set的size就是当前的答案。删掉当前的边，重复上面的操作。

#include <bits/stdc++.h>

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define all(a) (a).begin(), (a).end()

#define fillchar(a, x) memset(a, x, sizeof(a))

#define huan printf("\n");

#define debug(a,b) cout<<a<<" "<<b<<" ";

using namespace std;

const int maxn=2e5+;

typedef long long ll;

typedef pair<int,int> pii;

int du[maxn];

set<int> g[maxn];

int b1[maxn],b2[maxn],ans[maxn],vis[maxn];

int main()

{

    int n,m,k;

    scanf("%d%d%d",&n,&m,&k);

    set<pii> s;

    for(int i=;i<m;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        b1[i]=x,b2[i]=y;

        du[x]++,du[y]++;

        g[x].insert(y),g[y].insert(x);

    }

    for(int i=;i<=n;i++)

        s.insert(mp(du[i],i));

    for(int i=m-;i>=;i--)

    {

        while(s.size()>=)

        {

            auto itt=(*s.begin());

            if(itt.fi>=k)break;

            for(auto it=g[itt.se].begin();it!=g[itt.se].end();it++)

            {

                int u=*it;

                if(vis[u]==)continue;

                s.erase(mp(du[u],u));

                du[u]--;

                s.insert(mp(du[u],u));

                g[u].erase(itt.se);

            }

            s.erase(itt);

            vis[itt.se]=;

        }

        ans[i]=s.size();

        if(vis[b1[i]]==&&vis[b2[i]]==)

        {

            s.erase(mp(du[b1[i]],b1[i]));

            du[b1[i]]--;

            s.insert(mp(du[b1[i]],b1[i]));

            g[b1[i]].erase(b2[i]);

            s.erase(mp(du[b2[i]],b2[i]));

            du[b2[i]]--;

            s.insert(mp(du[b2[i]],b2[i]));

            g[b2[i]].erase(b1[i]);

        }

    }

    for(int i=;i<m;i++)

        printf("%d\n",ans[i]);

}