codeforces 1037E. Trips（倒叙）

题目传送门：

解题思路：

正着搞好像有点恶心。

反着搞。

一边删一边搞，从崩坏的地方开始，入度--。

最后dfs崩坏，更新答案。

注意要把边删掉防止重复崩坏。

代码：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 struct pnt{

     int hd;

     int ind;

     bool ded;

 }p[];

 struct ent{

     int twd;

     int lst;

 }e[];

 int cnt;

 int n,m,k;

 int lft;

 int ans[];

 int u[],v[];

 void ade(int f,int t)

 {

     cnt++;

     e[cnt].twd=t;

     e[cnt].lst=p[f].hd;

     p[f].hd=cnt;

     p[f].ind++;

     return ;

 }

 void Delete(int x)

 {

     if(p[x].ded)

         return ;

     p[x].ded=true;

     lft--;

     for(int i=p[x].hd;i;i=e[i].lst)

     {

         int to=e[i].twd;

         p[to].ind--;

         if(p[to].ind<k)

             Delete(to);

     }

     return ;

 }

 int main()

 {

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

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

     {

         scanf("%d%d",&u[i],&v[i]);

         ade(u[i],v[i]);

         ade(v[i],u[i]);

     }

     lft=n;

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

     {

         if(p[i].ind<k)

         {

             Delete(i);

         }

     }

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

     {

         ans[i]=lft;

         p[u[i]].hd=e[p[u[i]].hd].lst;

         p[v[i]].hd=e[p[v[i]].hd].lst;

         if(!p[v[i]].ded)

             p[u[i]].ind--;

         if(!p[u[i]].ded)

             p[v[i]].ind--;

         if(p[v[i]].ind<k)

             Delete(v[i]);

         if(p[u[i]].ind<k)

             Delete(u[i]);

     }

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

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

     return ;

 }