# Top Trading Cycle (最適循環交易法)
## Definition
**Top trading cycle (TTC)** is an algorithm for trading indivisible items without using money
* 在**不使用金錢**交易
* 每人只有**一個物品**可以交易
## How does it work ? & Example
**The algorithm works as follows :**
* 詢問每個人想交換的**志願序**
* 不須列出志願序**低於**自身的 ( i.e. 維持現狀比交易好 )

進而列出表格 :
| Agent | A | B | C | D | E | F | G |
| ---------- | --- | --- | --- | --- | --- | --- | --- |
| 1st choice | E | C | D | A | D | G | A |
| 2nd choice | F | D | E | B | E | A | G |
| 3rd choice | G | E | B | C | | B | |
| 4th choice | A | F | G | D | | C | |
| 5th choice | | G | A | | | D | |
| 6th choice | | A | C | | | E | |
| 7th choice | | | | | | F | |
* 畫出每個人**指向自己最高志願序**的箭頭
* 觀察是否可以**形成一個環**
* 若可以形成**環** , ==將環去除== i.e. 形成環的人交易 (==自身可以形成一環==)
* 繼續上述的步驟

**In this example :**
在第一志願序中 :
A ⇒ E , D ⇒ A , E ⇒ D ( 形成一個環 ! )
* 將他們都標記 (其他人無法再跟他們交易)

接下來的志願序中 : ( 對於每個人最好的志願序中 )
B ⇒ C , C ⇒ B , F ⇒ G , G ⇒ G
(B,C形成一環) (G自環) (F維持原樣)

**result :**
| Agent | A | B | C | D | E | F | G |
| ---------- | --- | --- | --- | --- | --- | --- | --- |
| 1st choice | E | C | | A | D | | |
| 2nd choice | | | | | | | G |
| 3rd choice | | | B | | | | |
| 4th choice | | | | | | | |
| 5th choice | | | | | | | |
| 6th choice | | | | | | | |
| 7th choice | | | | | | F | |

## Turn TTC to code

[Run my code online](https://repl.it/@jason810496/TopTradingCycle#main.cpp)

#include<bits/stdc++.h>
using namespace std;
int n,cycle_cnt=0,cnt=0;
vector<bool> visited_list;
vector<vector<int> > graph;
void trans(string temp,int i){
    stringstream ss;
    int num;
    ss.str(temp);
    while(ss>>num){
        num--;
        graph[i].push_back(num);
    }
}
void input(){
    string temp;
    cout<<"Top Trading Cycle Algorithm\n";
    cout<<"There are N items in this case\n";
    cout<<"Input N : ",cin>>n,cout<<'\n';
    graph.resize(n),visited_list.resize(n);
    cout<<"For each case :\ninput your item's number which you want to exchange";
    cout<<"form Top\"(most preferred) to low , until your item\n";
    cout<<"(including your item i.e. exchanged situation is worst than original situation)\n";
    cout<<"Eg : case 1: 3 4 2 5 1\n";
    cout<<" input data in form of :\nnum_i num_j num_k ... ( with space between each number)\n\n";
    getline(cin,temp);
    for(int i=0;i<n;i++){
        cout<<"For case "<<i+1<<" , input your sequences :\n";
        getline(cin,temp);
        trans(temp,i);
    }
    cout<<'\n';
}
void DFS_cycle(int cur,set<int> s,vector<int> cycle_list){
    if(s.find(cur)!=s.end()){
        cycle_cnt++;
        int ele_cnt=0;
        bool index=false;
        for(auto &i:cycle_list){
            if(i==cur){
                cout<<"cycle "<<cycle_cnt<<" :\n";
                index=true;
            }
            if(index){
                cout<<i+1<<' ';
                cnt++;
                ele_cnt++;
                visited_list[i]=1;
            }
        }
        if(ele_cnt==1){
            cout<<" (original situation is better)";
        }
        cout<<'\n';
        return;
    }
    s.insert(cur);
    cycle_list.push_back(cur);
    for(auto i:graph[cur]){
        if(!visited_list[i]){
            DFS_cycle(i,s,cycle_list);
            break;
        }
    }
}
void check(){
    cycle_cnt=0;
    cnt=0;
    while(cnt<n){
        for(int i=0;i<n;i++){
            if(visited_list[i]) continue;
            for(auto &j:graph[i]){
                if(!visited_list[j]){
                    set<int> s;
                    vector<int> cycle_list;
                    s.insert(i),cycle_list.push_back(i);
                    DFS_cycle(j,s,cycle_list);
                    break;
                }
            }
        }
    }
}
int main(){
    input();
    check();
    return 0;
}