链接
背景
\(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'&&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;
}
转载于:https://www.cnblogs.com/Peter0701/p/11342748.html
相关资源：JAVA上百实例源码以及开源项目
