 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
忍不住把程序前加了些....../*
▓▓▓▓▓▓▓▓▓▓▓▓▓█▀Γ ,░░░░░░Θ█▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒
▓▓▓▓▓▓▓▓▓▓█╜ ,▄▄▓▓▓▓▓▓▓▓▓▓▓▓▓▓▄╬▒█▓▓▓▓▓▓██▀ΘΘ░░░░░░░░░░░░░É▀██▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒
▓▓▓▓▓▓▓▓█░╓╣▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓░░░░░░░░░░░░░░░░░░░░░░░░░░░░░Θ█▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒
▓▓▓▓▓▓▓░╓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓Θ░░░░░Θ█▒░░░ ░░░░░░░░'░░░░░░░░░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▓▓▓▒▒▒▒▒▒
▓▓▓▓▓▓░▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒ΘΘΘΘ░░░░Θ░░░░╦░ ░░░δ░δδ░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓█Θ░░░░'' ░░░░░░░░░ ░░░░╫╣╬░█▓▓▓▓▓▒▓▓▓▓▓▓▓▓▒▒▒▒▒▒
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓Θ░░░ -░░░` ░░╢░░▒▒╬▓▓▓▓▒▓▒▒▒▓▓▓▒▓▓▒▒▒▒
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░ -⌐ "░╢╖⌐. '░╢░░░╠▒╣▓▓▓▓▓▒▓▒▒▒▒▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░░ ,╥╢░ - -░ ░╢╦µ "░╢░░░╠▒▓▓▓▓▓▓▒▒▒▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░'.╣╣░░ -░ ░░ .░░ ░░▒▄ ░╢░░╢░╫▓▓▓▓▓▓▒▓▓▓▓▓▒▒▒
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░░ ╔▒░░ ╤░ ░░ ░▓░ ░ ░ ⌐░╢▓µ ░░░░░░╢▓░█▓▓▒▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░' ╥▒░░ ╓╣░ ╫▒░ -╫▒╕ ░░ ░░ ░░╠▓╕ ░░░░░░░╢▓╣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;
}
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
