背景
(18th) (Polish) (Olympiad) (in) (Informatics) (Round3) (Day1) (A) 题， (Luogu) (P3524/BZOJ2530)
题意
给定一张 (n) 个点 (m) 条边的图，保证图中有一个 (frac{2}{3}n) 大小的团。求出其中任意 (frac{1}{3}n) 个点的编号，按递增顺序排列。有 (SPJ) 。
解法
(O(n^2)) 标记两点间没有边的点的编号。具体来说，每次枚举一个未标记的点 (i) ，找到第一个编号比其大且未标记的不连通的点 (j) ，标记 (i) 和 (j) 两个点，枚举下一个点。
标记完后，按递增顺序输出前 (frac{1}{3}n) 个未标记的点即可。
细节
(1.) 标记 (i) 和 (j) 两个点，一定要枚举下一个点。（注意！！！）
代码
$View$ $Code$
//省略头文件 using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int n,m,x,y,cnt; bool vis[3005],g[3005][3005]; int main() { n=read(); m=read(); for(register int i=1;i<=m;i++) { x=read(); y=read(); g[x][y]=1; g[y][x]=1; } for(register int i=1;i<=n;i++) { if(!vis[i]) { for(register int j=i+1;j<=n;j++) { if((!vis[j])&&(!g[i][j])) { vis[i]=1; vis[j]=1; break; } } } } int std=n/3; for(register int i=1;i<=n;i++) { if(!vis[i]) { printf("%d ",i); cnt++; } if(cnt==std) return 0; } return 0; }