bzoj 1098 办公楼biu —

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1098

首先，没有连边的人一定得在一个连通块里；

先把所有人连成一个链表，然后从第一个人开始，把和它有连边的人都打上标记，没有标记的就加入栈里，并在链表中删除；

只要栈里还有值，就重复这个操作，把必须和栈顶元素在一个连通块的元素也都找出来加入栈，同时 siz++；

因为链表维护，所以遍历人的复杂度总体是 O(n) 的，再加上遍历边的复杂度，算下来是 O(n+m)；

关键在于用链表降低遍历人的复杂度！很好的思路。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const xn=1e5+,xm=2e6+;

int n,m,hd[xn],ct,to[xm<<],nxt[xm<<],vis[xn],pr[xn],nt[xn],siz[xn],cnt;

int sta[xn],top;

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return f?ret:-ret;

}

void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}

void del(int x){nt[pr[x]]=nt[x]; pr[nt[x]]=pr[x];}

int main()

{

  n=rd(); m=rd();

  for(int i=,x,y;i<=m;i++)

    {

      x=rd(); y=rd();

      add(x,y); add(y,x);

    }

  for(int i=;i<=n;i++)pr[i]=i-,nt[i]=i+;

  int i=; nt[]=; pr[n+]=n;

  while(nt[]!=n+)

    {

      i=nt[]; del(i);

      for(int j=hd[i];j;j=nxt[j])vis[to[j]]=i;

      sta[++top]=i; siz[++cnt]=;

      while(top)

    {

      int x=sta[top]; top--;

      for(int k=hd[x];k;k=nxt[k])vis[to[k]]=x; vis[x]=x;

      int nww=nt[];

      while(nww!=n+)

        {

          if(vis[nww]!=x)siz[cnt]++,sta[++top]=nww,del(nww);

          nww=nt[nww];

        }

    }

    }

  printf("%d\n",cnt);

  sort(siz+,siz+cnt+);

  for(int i=;i<=cnt;i++)printf("%d ",siz[i]);

  return ;

}

巴特西

bzoj 1098 办公楼biu —— 链表+栈

最新文章

热门文章