Codeforces Round #22 (Div 2 only) C. System Administrator

Codeforces グラフ理論

問題概要

n個の頂点をm本の辺でつないだ、次の条件を満たすような無向グラフを作り、グラフを辺リスト表現で出力せよ。

  • グラフの頂点は1〜nの番号をもつ。
  • グラフは連結である。
  • グラフから頂点vを取り除くと連結ではなくなる。

このようなグラフを作ることが不可能の場合-1を出力せよ。
3≤n≤10^5, m≤10^5を満たす

解法

頂点がn個で、条件を満たすグラフの辺の本数として可能な範囲を考える。
まず、連結であることからm≥n-1.
上限についてはvを取り除いた後にできる二つグラフの頂点の数をa,bとすれば
m≤C(a+1,2)+C(b+1,2)である。nを固定したときこれが最大になるのはa,bのどちらかが1のときである。


以上のような考察から、mが上の範囲にないときは-1を出力し,
あるときは1個の頂点をグループA,Aの１個とvを除いた残りの頂点をグループBとして、
まずvとA,Bの各頂点をつなぎ、残りは適当に数をあわせてBグループ内の頂点をつないで出力すればよい。

ソースコード

void run()
{
        int n,m,v; cin>>n>>m>>v;
        if(!ok(n,m))
        {
                cout<<-1<<endl; return;
        }
        vi g1,g2; int ng1=0,ng2=0;
        rep(i,n)if(i+1!=v)
        {
                if(ng1<1)g1.pb(i+1),ng1++;
                else g2.pb(i+1),ng2++;
        }
        rep(i,ng1)cout<<v<<" "<<g1[i]<<endl;
        rep(i,ng2)cout<<v<<" "<<g2[i]<<endl;
        m-=ng1+ng2;
        if(m>0)rep(i,ng1)rep(j,i)
        {
                
                cout<<g1[i]<<" "<<g1[j]<<endl;
                if(--m==0)return;
        }
        if(m>0)rep(i,ng2)rep(j,i)
        {
                cout<<g2[i]<<" "<<g2[j]<<endl;
                if(--m==0)return;
        }
}