Cycles

先构造完全图,然后根据完全图构造非完全图即可.

#include <bits/stdc++.h>
using namespace std;
const int N=105;
int c_3[N],c_2[N*5];
int ans[N][N];
int main()
{
    int n;
    c_3[3]=1;c_2[2]=1;
    for(int i=4;i<=100;i++)
    {
        c_3[i]=c_3[i-1]*i/(i-3);
    }
    for(int i=3;i<=500;i++)
    {
        c_2[i]=c_2[i-1]*i/(i-2);
    }
    scanf("%d",&n);
    int cnt=0;
    for(int i=100;i>=3;i--)
    {
        if(c_3[i]<=n) {n-=c_3[i];cnt=i;break;}
    }
    //造cnt个完全图.
    vector<int>v;
    for(int i=cnt;i>=2;i--)
    {
        if(n==0) break;
        while(n>=c_2[i]) {v.push_back(i);n-=c_2[i];}
    }
    int vnt=v.size();
    //vnt个非完全图.
    cout<<cnt+vnt<<endl;
    for(int i=1;i<=cnt;i++)
    {
        for(int j=1;j<=cnt;j++)
        {
            if(i!=j) ans[i][j]=1;
        }
    }
    for(int i=0;i<vnt;i++)
    {
        for(int j=1;j<=v[i];j++)
        {
            ans[i+1+cnt][j]=1;
            ans[j][i+1+cnt]=1;
        }
    }
    for(int i=1;i<=cnt+vnt;i++)
    {
        for(int j=1;j<=cnt+vnt;j++)
        {
            printf("%d",ans[i][j]);
        }puts("");
    }puts("");
    return 0;
}