[HOJ 293][Codeforces #192]Graph Reconstruction

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

可以發現，因為每個點的度數都<=2，因此分岔是不可能存在的，所以整張圖就是: 一些點、幾條線、幾個圈，其中點可以視為大小1(長度0)的線
總之，先把這些線和圈找出來，存起來，假設待會會用到(?)
先來討論圈，因為看起來比較簡單(?)
一個圈在甚麼情況下可以變成另外一個圈又符合題目指定的條件呢?
首先可以發現，圈的大小<=4時是不行的，不然的話：
1. 如果圈的大小是奇數
可以在圈上每隔兩格把點連起來，這樣跑完兩圈剛好回到原點，也把所有的點都經過了
2. 如果是偶數
可以從1兩格兩格跳到n-1，再跳到2，然後回到n，再兩格兩格跳回4

線的話也可以照做

我們先來盡量找出合法的邊，並盡量拼成一個圈(可以證明圈是符合條件中最好(邊數最大化)的選擇之一)

現在，假設我們拼出了大小n的合法圈，那麼所有長度<=n的線和圈都可以merge進這個大圈裡面了(方法是將圈的每一個邊拆開，接上目標的每一個點)
所以，我們可以先把這些線和圈依照大小作排序，大的排前
如果第一個線或圈就可以自己變成合法的圈，可以發現，接下來因為大小是遞減的，照著上面的方法一個一個merge完就全部結束了

如果第一個線或圈不能自己變成新圈，那麼可以考慮和第二個線或圈合併討論，或連第三個也一起加進來......，好像變得很複雜= =

我們可以將邊分為兩類：不合法邊(也就是原圖的邊，程式碼中Edge.type=0)和合法邊(Edge.type=1)
因此，可以構造一個策略，先將線和圈的邊用不合法的身分push進queue裡面，然後對於之後的線或圈，就可以用「以一個點和一條不合法邊換取兩條合法邊」的策略了
仔細想想就會發現更好的策略是不可能的

請注意以下狀況：
如果是大小4的圈，轉換成不合法邊*2+合法邊*2是最優的
    (不合法:(1,4),(2,3)，合法:(1,3),(2,4))
如果是大小4的線，轉換成不合法邊*1+合法邊*3是最優的
    (不合法:(2,3)，合法:(1,3),(1,4),(2,4))
如果是大小3的線，轉換成不合法邊*2+合法邊*1是最優的
    (不合法:(1,2),(2,3)，合法:(1,3))
剩餘的，都只能轉換成不合法邊*線或圈的大小

如果最後不合法邊都不見了，那麼就可以保證答案不是-1(想一想，為甚麼XD)
不然的話，把不合法邊都pop掉，看看剩餘的合法邊數量有沒有大於M
結束(好難解釋啊QAQ)

對了，這裡提供一個簡單的測資讓你debug用：
4 3
1 2
2 3
3 4

code:

#include<cstdio>
#include<vector>
#include<cassert>
#include<queue>
#include<algorithm>
using namespace std;
int N,M;
struct Edge
{
    int a,b,type;
    Edge(){}
    Edge(const int _a,const int _b,const int _t):a(_a),b(_b),type(_t){}
    bool operator<(const Edge &e)const
    {
        if(type!=e.type)return type<e.type;
        return a!=e.a?a<e.a:b<e.b;
    }
};
struct Link
{
    vector<int>s;
    int type;
    Link(){}
    Link(const vector<int>&_s,const int _type):s(_s),type(_type){}
    int size()const{return s.size();}
    bool operator<(const Link &l)const{return size()!=l.size()?size()>l.size():type<l.type;}
    int operator[](const int idx)const{return s[idx];}
};
queue<Edge>ANS;
vector<int>ET[100000];
bool VIS[100000];
vector<Link>LINK;
void Dfs(const int u,vector<int>&link)
{
    assert(!VIS[u]);
    VIS[u]=true;
    link.push_back(u);
    int cnt=0;
    for(const int nxt:ET[u])if(!VIS[nxt])Dfs(nxt,link),cnt++;
    assert(cnt<=1);
}
void AddEdge(const int a,const int b,const int type){ANS.push(Edge(a,b,type));}
bool Solve()
{
    if(N<=2)return M==0;
    for(int i=0;i<N;i++)VIS[i]=false;
    LINK.clear();
    for(int i=0;i<N;i++)if((int)ET[i].size()==1&&!VIS[i])
    {
        vector<int>s;Dfs(i,s);
        LINK.push_back(Link(s,0));
    }
    for(int i=0;i<N;i++)if(!VIS[i])
    {
        vector<int>s;Dfs(i,s);
        LINK.push_back(Link(s,1));
    }
    sort(LINK.begin(),LINK.end());
    while(!ANS.empty())ANS.pop();
    const int l0sz=LINK[0].size();
    if(l0sz==1)
    {
        assert((int)LINK.size()>=2);
        AddEdge(LINK[0][0],LINK[1][0],1);
        for(int i=0;i<2;i++)LINK.erase(LINK.begin());
    }
    else if(l0sz==2||l0sz==3)
    {
        const Link &s=LINK[0];
        if(l0sz==3&&s.type==0)AddEdge(s[0],s[1],0),AddEdge(s[1],s[2],0),AddEdge(s[0],s[2],1);
        else for(int i=0;i<l0sz;i++)AddEdge(s[i],s[(i+1)%l0sz],0);
        LINK.erase(LINK.begin());
    }
    else if(l0sz==4)
    {
        const Link &s=LINK[0];
        AddEdge(s[1],s[2],0);
        AddEdge(s[0],s[3],s.type^1);
        AddEdge(s[0],s[2],1),AddEdge(s[1],s[3],1);
        LINK.erase(LINK.begin());
    }
    else if(l0sz>=5)
    {
        const int n=LINK[0].size();
        vector<int>tmp;
        int cur=0;
        while(cur<n)tmp.push_back(cur),cur+=2;
        if(cur==n)
        {
            tmp.push_back(1),cur=n-1;
            while(cur>1)tmp.push_back(cur),cur-=2;
        }
        else
        {
            cur=1;
            while(cur<n)tmp.push_back(cur),cur+=2;
        }
        assert((int)tmp.size()==n);
        for(int i=0;i<n;i++)AddEdge(LINK[0][tmp[i]],LINK[0][tmp[(i+1)%n]],1);
        tmp.clear(),vector<int>().swap(tmp);
        LINK.erase(LINK.begin());
    }
    else assert(0);
    for(const auto &s:LINK)
    {
        for(int i=0;i<(int)s.size();i++)
        {
            ANS.push(Edge(ANS.front().a,s[i],1));
            ANS.push(Edge(s[i],ANS.front().b,1));
            ANS.pop();
        }
    }
    while(!ANS.empty()&&(ANS.front().type==0||(int)ANS.size()>M))ANS.pop();
    return (int)ANS.size()==M;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)==2)
    {
        for(int i=0;i<N;i++)ET[i].clear();
        for(int i=0,a,b;i<M;i++)
        {
            scanf("%d%d",&a,&b),a--,b--;
            ET[a].push_back(b),ET[b].push_back(a);
        }
        if(Solve())while(!ANS.empty())printf("%d %d\n",ANS.front().a+1,ANS.front().b+1),ANS.pop();
        else puts("-1");
        break;
    }
    return 0;
}
/*
4 3
1 2
2 3
3 4
*/