> /*
> ▓▓▓▓▓▓▓▓▓▓▓▓▓█▀Γ     ,░░░░░░Θ█▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒
> ▓▓▓▓▓▓▓▓▓▓█╜ ,▄▄▓▓▓▓▓▓▓▓▓▓▓▓▓▓▄╬▒█▓▓▓▓▓▓██▀ΘΘ░░░░░░░░░░░░░É▀██▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒
> ▓▓▓▓▓▓▓▓█░╓╣▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓░░░░░░░░░░░░░░░░░░░░░░░░░░░░░Θ█▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒
> ▓▓▓▓▓▓▓░╓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓Θ░░░░░Θ█▒░░░  ░░░░░░░░'░░░░░░░░░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▓▓▓▒▒▒▒▒▒
> ▓▓▓▓▓▓░▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒ΘΘΘΘ░░░░Θ░░░░╦░               ░░░δ░δδ░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓█Θ░░░░''      ░░░░░░░░░                        ░░░░╫╣╬░█▓▓▓▓▓▒▓▓▓▓▓▓▓▓▒▒▒▒▒▒
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓Θ░░░         -░░░`                                 ░░╢░░▒▒╬▓▓▓▓▒▓▒▒▒▓▓▓▒▓▓▒▒▒▒
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░    -⌐                                     "░╢╖⌐.  '░╢░░░╠▒╣▓▓▓▓▓▒▓▒▒▒▒▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░░ ,╥╢░             -     -░                     ░╢╦µ   "░╢░░░╠▒▓▓▓▓▓▓▒▒▒▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░'.╣╣░░       -░    ░░    .░░                      ░░▒▄    ░╢░░╢░╫▓▓▓▓▓▓▒▓▓▓▓▓▒▒▒
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░░ ╔▒░░        ╤░    ░░     ░▓░      ░     ░          ⌐░╢▓µ   ░░░░░░╢▓░█▓▓▒▓▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░' ╥▒░░       ╓╣░    ╫▒░    -╫▒╕      ░░    ░░          ░░╠▓╕  ░░░░░░░╢▓╣S▓▓▓▓▒▒▒▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓░░░  ║▓░░        ╣░░   ]▒░  '  ╠▓╠▌      ░▒░    ░╦       ░░ ░░║▓µ  ░░░╠░░░╫▓╣░▓▓▒▓▒▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓Θ░░░ ║▓░░   -    ╫Θ░░   ╫Θ░  ⌐ !▒Θ░▒   ░  ░░▓⌐   ░╢▌       ░░ ░░╢▓   ░░░░░╣░▒▌░╣▓▒▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▒░░░ ╓▓░░   ░⌐   ╠▌░░   ╔▒░░ ░  ║▓░░╫▌  ░░ ¡░╢▌    ░╫▓⌐      ░░░░░╫▌  ░░░░░░░░▓▓▓▓▓▒▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓░░░ ╓▓░░░  ░░   ╓▓░░░   ╫Θ░  ░  ╫▒░░░▓µ  ░  ░░▒╕   '░╫▌µ      ░░░░░▓µ  ░░░░░░░╫▒Θ▓▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓Θ░░⌐╓▓▓░░░ ░░⌐  .╣▒░░   ]▓░░░░░ ]▓░░░░║▓  ░╦⌐░░╠▓µ   ░░▓▓╦      ░░░░╫▌   ░░░░░░║▓░░▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓░░░╓▓▒▒░░⌐░╢░   ║▓░░░   ║▓░░░░⌐ ╠▒░░  ░╫▌  ╠░░░░▓▓   "░░▓▓░░     ░░░╠▒µ   ░░░░░░▓░░╚▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓░░░╫▒╫Θ░░░░░░  ╔▓▒░░░   ╫▌░░░░  ▒░░░   ░▒╕ \░░░░╠▓▌   ░╢╠▓▓░░⌐    ░░░╫░   ░░░░░░▒▌░░▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▌░░╫▓░╣░░░░░░⌐  ╫▒▒░░░  ]▓▌░░░░ ]▒░░     ░▒╕ ░░░░░╫▓▌   ░░╢▒▒▒░░⌐   ░░╫▌   ░░░░░░║▌░▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▌░╢▓▓░╣░░░░░░  ╠▒╢▓░░░  ╫▒▒░░░░ ║▒░░      ░▒╕ ░░░░░▓▒▌  \░░╢▓δ▓░╣░  '░╢▓░  ░░░░░░╠▓▓▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▌╠▓▓▓░╣╣░░░░░⌐ ▒░╫▒░░░ ]▒╣▒░░░░ ╫░░░       ╙▒Q ░░░░╢▓▒▓  "░░╢▓░▒╣░░░ ░╢▓░  ░░░░░░╠▓░╫▓▓▓▓▒▒
> ▓▓▓▓▓▓▓▓▓▌╫▓▓▓░╫▒░░░░░ ║▒░║▓░░░ ║▒░▒░░░░]▒░░         `▒▌ ░░░░╫▒░▓╕ ░░░▒▌░Θ▓░░░░░▒C  ░░░╢░░▐▓░░╫▓▒▒▒▒
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▌░╫▓░░░░░.╫░░▐▓░░░ ▒░░╫╣░░░]▒░░           ╙▓╕░╢░░▒░░Θ▒µ⌠░╣╫▒░░╫▓░░░▒▌  ░░░░░░▐▓░╢▓▒▒▒▒▒
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▌░░▓░░░░░▐▒░░ ╫▒░░░▒░░║▓░░░▐▒░░            '▒╦░░╢╠▓░░╙▀╦░░░▒▓░░░▒╣░▒▌░ ░░░░╢░▐▓▓▓▒▒▒▒▒▒
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▌░░║▓░░░░╫▌░░ ╚▓░░░▒░░░╢▌░░╠▌░░              ╙▒░░░╫▒░░⌐ ▀▒░░╢▓░░░Θ▓▒▌░⌐░╢░░░░╠▓▒▓▒▒▒▒▒▒
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▌░░░╫▓╢░░▒░êè╗╗╣▓░░▒░░ '╫░░╠▒░░                ╙▒╣░▒░░░  ,╠▒▓╣▓▒▒Θ░▒░░⌐░░░╣░░╠▓░╫▓▒▒▒▒▒
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▌░░░░╫▓░░▒░░░░░░║▒Θ▓█▓▓▓▄▓▓╢▒░░                 ,▄▓▓▓▓▓▓▓╢░░▄░▒▓▒░░▒░░░░░░░░░╠▓░║▓╣▒▒▒▒
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▌░░ ░╣╚▓░▒░▄▄▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▄              ▄╬▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓██▓▓▓▒░░░░░░░░░╠▓╣▓▒▒▒▒╣▒
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▌░░ ░░░║▓▓▓▓█δ░ ╫▓▓▓▓▓▓▓▓▓▓▓▓ΘÑδòµ        ⌐ôΘ░░║▓▀▓▓▓▓▓▓▓▓▓▓▓▌░░░▓▓▒░░░░░░░░░║▓▒▒▒▒▒╣▒▒
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▌░░ ░░░▐▓░░▒░"  ╙▀▀█▓▓▓▓▓▓▓░"δ░              '░╜  `^`▓▓▓▓▓▓▓▓▌'░╢Ö░▒░░░░░░░╣░║▓▒▒▒▒▒▒▒▒
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▌░░ ░░░░╫▓░░░   ╫▓▓▓▓▓▓▓▓▓▓░                     '▓▓▒▒▓▓▓▒▒▒▓░╓░░░╠▌░░░░░╣░░░╫▓▓▓▓╣▒▒▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▌░░ ░░░░╢▓░░⌐ "è▄▓▓╣╣╢╣╬╣▓▓░                     :██▒▒▓▓▓▓▓▓█ò░░░░╫Θ░╢░░╣░╢░░▓▓▓▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▌░░ ░░'░░▓▓░    ``▀▀▀▀Γ``                                 ⌐░░░░░░░╫░░░░░░░░░░▓▓▓▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░⌐   ░░▒▓▌░                                             ░░░░░░░╣▓⌐░╢░░░░╣░║▓▓▒▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░ ░ ░░╫▒▒▌                                            ░░░░░░░╫▒▒ ░░░░░╢╣░╫▓▒▒▒▒▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓░╣░   ░░╢▓░▒▄                                          '░░░░░░╠▓╣▌ ░╢░░░░╢░▓▓▒▒▒▒▒▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓░▒░⌐  ░░╫▓▓╣▓╕ '                     ░░⌐               ░░░░░░║▓▓▓▌ ░╢░░░╢░║▓▓▒▒▒▒▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓░╫░░ ░░╢║▓▓▓▓▓▄                     ░░░░⌐             ░░░░░░║▓▓▓▓░ ░░░░░╣░▓▓▓▓▓▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒╫▌   ░░╠▓▓▓▓▓▓▓▄                     '              ░░░░░╓▓▓▓▓▓▌  ░╢░╣░╣╢▓▓▓▓▓▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▒▓▓╫▓░  ░╢╢▓▓▓▓▓▓▓▓▓▄             ╙╜╨╨╨╨╨ÉSê░         ░░░░╓╬▓▓▓▓▓▓▌' ░╢╣╣╢░╫▓▓▓▓▓▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓╣▓▓╢▓░  ░░╢▓▓▓▓▓▓▓▓▓▓▓▄                             ⌐░░░╥▓▓▓▓▓▓▓▓▓░░ ░╢░╣╢░▓▓▓▓▓▓▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░▓░  ░╢╠▓▓▓▓▓▓▓▓▓▓▓▓▓▓▄                        ⌐░░░╣▓▓▓▓▓▓▓▓▓▓▓░░░░╢░╣░╫▓▓▓▓▓▓▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▌▒░░⌐░░╢▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓╦µ                    ░╓╗▒Θ╫▓▓▓▓▓▓▓▓▓▓▓ ╫░░╢░░░▓▓▓▓▓▓▓▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓╢▒░ ░╢╢▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░╙▒╦µ               ╔╣▒Θ░░░╫▓▓▓▓▓▓▓▓▓▓▌░▒⌐░╢░░╫▓▓▓▓▓▓▓▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓╣▓░░░╢╢▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░   ╙δ╣╦,      ,╓╗▒▒░░░░░░░╫▓▓▓▓▓▓▓▓▓▓▌▐▒⌐░╢╢░▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░╢╢▓▓▓▓▓▓▓▓▓▓▓█▓▓▓▓░      `ÉΘ▒▒▒▒ΘΘ░░░░░░░░░░░╢▓▓▓▓▓▓▓▓▓▓▌╠▒░╠╢░╫▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░╢╢▓▓▓▓▓▓▓▓▓▓░░░░╙▀▀▀▀▀▀S▒▒▒▒▒▒▒╣╣╣▒▒╬▒▒▒▒▒▒▒▓▓▓▒▒╣╫▓▓▓▓▓▌║▌⌐░░░▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓╣░╢╢▓▓▓▓▓▓▓▓▓▒╫▓▓▓▓▄▄▄▄,,,        ░░░░╢╢╣╣╣╣╣╣▓▓▓▓▓▓▓▓▓▓▓▓▌╫▌ ░░╫▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
> ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░╫▓▓▓▓▓▓▓▓╬▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓µ╔▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▌▒▌ ░╠▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
>  
>  888    d8P    d8b                                      d8888             888      888
>  888   d8P     Y8P                                     d88888             888      888
>  888  d8P                                             d88P888             888      888
>  888d88K       888   88888b.     .d88b.              d88P 888   888d888   888888   88888b.    888  888   888d888
>  8888888b      888   888 "88b   d88P"88b            d88P  888   888P"     888      888 "88b   888  888   888P"
>  888  Y88b     888   888  888   888  888           d88P   888   888       888      888  888   888  888   888
>  888   Y88b    888   888  888   Y88b 888          d8888888888   888       Y88b.    888  888   Y88b 888   888
>  888    Y88b   888   888  888    "Y88888         d88P     888   888        "Y888   888  888    "Y88888   888
>                                      888
>                                 Y8b d88P
>                                  "Y88P"
>  .d8888b.               888
> d88P  Y88b              888
> Y88b.                   888
>  "Y888b.      8888b.    88888b.     .d88b.    888d888
>     "Y88b.       "88b   888 "88b   d8P  Y8b   888P"
>       "888   .d888888   888  888   88888888   888
> Y88b  d88P   888  888   888 d88P   Y8b.       888
>  "Y8888P"    "Y888888   88888P"     "Y8888    888
> */
> #include<iostream>
> #include<cstdio>
> #include<cstring>
> #include<algorithm>
> #include<stack>
> #include<queue>
> using namespace std;
> const int Maxn=1010,Maxm=1000010;
> struct edge{
>     int v,nxt;
> }e[Maxm*2];
> struct pr{
>     int u,v;
>     pr(){}
>     pr(int U,int V){u=U;v=V;}
> }st[2*Maxm];
> int n,m,tot,ans,top,head[Maxn],dfn[Maxn],low[Maxn],col[Maxn];
> bool hate[Maxn][Maxn],vis[Maxn],cntd[Maxn],sta[Maxn];
> int q[Maxn];
> void addedge(int u,int v){
>     e[tot].v=v;
>     e[tot].nxt=head[u];
>     head[u]=tot++;
> }
> int count(){
>     int i,sum=0;
>     for(i=0;i<n;i++)if(sta[i]&&!cntd[i]){
>         cntd[i]=1;
>         sum++;
>     }
>     return sum;
> }
> int judge(int s){
>     int front=0,tail=0;
>     memset(col,-1,sizeof(col));
>     q[tail++]=s;
>     col[s]=0;
>     while(front!=tail){
>         int u=q[front++];
>         for(int i=head[u];~i;i=e[i].nxt){
>             int v=e[i].v;
>             if(!sta[v])continue;
>             if(~col[v]&&col[v]==col[u])return count();
>             if(col[v]==-1){
>                 q[tail++]=v;
>                 col[v]=(col[u]^1);
>             }
>         }
>     }
>     return 0;
> }
> void tarjan(int depth,int f,int u){
>     dfn[u]=low[u]=depth;
>     vis[u]=1;
>     st[top++]=pr(f,u);
>     int i;
>     for(i=head[u];~i;i=e[i].nxt){
>         int v=e[i].v;
>         if(v==f)continue;
>         if(vis[v]){low[u]=min(low[u],dfn[v]);continue;}
>         tarjan(depth+1,u,v);
>         low[u]=min(low[u],low[v]);
>         if(low[v]==depth){
>             memset(sta,0,sizeof(sta));
>             while(!(st[top].u==u&&st[top].v==v)){
>                 sta[st[--top].u]=1;sta[st[top].v]=1;
>             }
>             ans+=judge(v);
>         }
>     }
>     if(low[u]==depth)top--;
> }
> int main(){
>     ios::sync_with_stdio(0);
>     while(scanf("%d%d",&n,&m)){
>         if(!n&&!m)break;
>         tot=0;
>         memset(hate,0,sizeof(hate));
>         memset(cntd,0,sizeof(cntd));
>         memset(head,-1,sizeof(head));
>         memset(vis,0,sizeof(vis));
>         top=0;
>         int i,j;
>         for(i=0;i<m;i++){
>             int a,b;
>             scanf("%d%d",&a,&b);
>             a--,b--;
>             hate[a][b]=hate[b][a]=1;
>         }
>         for(i=0;i<n;i++)for(j=0;j<n;j++)if(i!=j&&!hate[i][j])addedge(i,j);
>         ans=0;
>         for(i=0;i<n;i++)if(!vis[i])tarjan(0,-1,i);
>         printf("%d\n",n-ans);
>     }
>     return 0;
> }

• Re:忍不住把程序前加了些...... (2) 1007816143 2015-09-04 11:51:24
  • Re:忍不住把程序前加了些...... (6) 914596827 2016-05-03 00:43:07
    • Re:忍不住把程序前加了些...... (2) 914596827 2016-05-03 00:43:26