HDU 4687 Boke and Tsukkomi (일반 그림 일치 | 꽃나무 포함)

경기 할 때 처음에 이 문 제 를 보 았 을 때 2 분 그림 이 일치 하 는 줄 알 았 는데 나중에 야 전혀 아니 라 는 것 을 알 게 되 었 다. 왜냐하면 이 문 제 는 길이 가 홀수 인 원 이 존재 하기 때문이다. 예 를 들 어 1 - > 2, 2 - > 3, 3 - > 1.그래서 이 문 제 는 일반 그림 과 일치 하 는 플 라 워 트 리 알고리즘 을 사용 해 야 한다.
경기 할 때 베 낀 템 플 릿 을 잘못 베 꼈 는데, 상술 한 사례 에 서 는 순환 이 나 타 났 다.  경기 후 문 제 를 보충 할 때 맵 으로 무 게 를 주 었 지만 정 답 을 얻 지 못 했 습 니 다. 왠 지 모 르 게 잠시 놓 고 아래 에 정확 한 해법 을 제시 하 겠 습 니 다. 
자세 한 참조 코드:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<list>
#include<cmath>
#include<set>
#include<queue>
using namespace std;
const int maxn = 55;
int n,m,Match[maxn],Head,Tail,Queue[maxn],Start,Finish,NewBase,Father[maxn],Base[maxn],cnt,Count;
bool InQueue[maxn],InPath[maxn],InBlossom[maxn],Graph[maxn][maxn];
void Push(int u) {
    Queue[Tail] = u;
    Tail++;
    InQueue[u] = true;
}
int Pop() {
    int res = Queue[Head];
    Head++;
    return res;
}
int FindCommonAncestor(int u,int v) {
    memset(InPath,false,sizeof(InPath));
    while(true) {
        u = Base[u];
        InPath[u] = true;
        if(u == Start) break;
        u = Father[Match[u]];
    }
    while(true) {
        v = Base[v];
        if(InPath[v])break;
        v = Father[Match[v]];
    }
    return v;
}
void ResetTrace(int u) {
    int v;
    while(Base[u] != NewBase) {
        v = Match[u];
        InBlossom[Base[u]] = InBlossom[Base[v]] = true;
        u = Father[v];
        if(Base[u] != NewBase) Father[u] = v;
    }
}
void BloosomContract(int u,int v) {
    NewBase = FindCommonAncestor(u,v);
    memset(InBlossom,false,sizeof(InBlossom));
    ResetTrace(u);
    ResetTrace(v);
    if(Base[u] != NewBase) Father[u] = v;
    if(Base[v] != NewBase) Father[v] = u;
    for(int tu = 1; tu <= n; tu++)
        if(InBlossom[Base[tu]]) {
            Base[tu] = NewBase;
            if(!InQueue[tu]) Push(tu);
        }
}
void FindAugmentingPath() {
    memset(InQueue,false,sizeof(InQueue));
    memset(Father,0,sizeof(Father));
    for(int i = 1; i <= n; i++)
        Base[i] = i;
    Head = Tail = 1;
    Push(Start);
    Finish = 0;
    while(Head < Tail) {
        int u = Pop();
        for(int v = 1; v <= n; v++)
            if(Graph[u][v] && (Base[u] != Base[v]) && (Match[u] != v)) {
                if((v == Start) || ((Match[v] > 0) && Father[Match[v]] > 0))
                    BloosomContract(u,v);
                else if(Father[v] == 0) {
                    Father[v] = u;
                    if(Match[v] > 0)
                        Push(Match[v]);
                    else {
                        Finish = v;
                        return;
                    }
                }
            }
    }
}
void AugmentPath() {
    int u,v,w;
    u = Finish;
    while(u > 0) {
        v = Father[u];
        w = Match[v];
        Match[v] = u;
        Match[u] = v;
        u = w;
    }
}
void Edmonds() {
    memset(Match,0,sizeof(Match));
    for(int u = 1; u <= n; u++)
        if(Match[u] == 0) {
            Start = u;
            FindAugmentingPath();
            if(Finish > 0)AugmentPath();
        }
}
int getMatch() {
    Edmonds();
    Count = 0;
    for(int u = 1; u <= n; u++)
        if(Match[u] > 0)
            Count++;
    return Count/2;
}
struct node {
    int a,b;
    node(int a=0,int b=0): a(a),b(b) {}
    bool operator < (const node& rhs) const {
        return a < rhs.a || (a == rhs.a && b < rhs.b);
    }
    bool operator == (const node& rhs)const {
        return a == rhs.a && b == rhs.b;
    }
} e[155],ee[155];
map<node,int> p;
void PrintMatch() {
    cnt = getMatch();
vector<int> ans;
    int g[maxn][maxn];
    memcpy(g,Graph,sizeof(g));
    for(int i=0;i<m;i++) {
        memcpy(Graph,g,sizeof(g));
        int u = e[i].a, v = e[i].b;
        for(int j = 1; j <= n; j++)
                Graph[j][u] = Graph[u][j] = Graph[j][v] = Graph[v][j] = false;
        int cur = getMatch();
        if(cur == cnt - 1) ;
        else ans.push_back(i+1);
    }
    int sz = ans.size();
        printf("%d
",sz);
        for(int i = 0;i < sz;i++)
        {
            printf("%d",ans[i]);
            if(i < sz-1)printf(" ");
        }
        printf("
");
}
int main() {
    while(~scanf("%d%d",&n,&m)) {
        memset(Graph,0,sizeof(Graph));
        for(int i=0; i<m; i++) {
            scanf("%d%d",&e[i].a,&e[i].b);
            Graph[e[i].a][e[i].b]=Graph[e[i].b][e[i].a]=true;
        }
        Edmonds();
        PrintMatch();
    }
    return 0;
}