2021 全國學科能力競賽模擬賽 2.BGP

內容目錄

前言

我發現，全國能力競賽的難度似乎與我預期的有落差，這一題也是我唯一一個完全解開的題目。真的好難！

題目敘述 :

「BGP 劫持（BGP Hijacking）」是⼀種透過「邊界閘道器協定（Border Gateway Protocol,BGP）」的性質進⾏攻擊的⼿段。簡單來說，每個伺服器會宣稱⾃⼰擁有⼀段 IP，並將這個訊息傳遞給周遭的伺服器，來更新他們的路由表。周遭的伺服器也會將這個更新繼續往外傳遞，使伺服器知道要如何將封包傳遞到指定的IP。而 BGP 劫持這個攻擊⼿法，就是透過錯誤地宣稱⾃⼰擁有某⼀段 IP，或者是⾃⼰通往擁有該 IP 的伺服器路徑更短，來使得其他路由器將 IP 往他傳遞。並透過 BGP 更新路由表的特性進⾏⼤規模的流量轉移，使得使⽤者無法存取特定的服務，或者是拿到封包之後拆解其中的內容以獲得敏感資訊。

現在，全國資訊安全能⼒競賽模擬賽要進⾏⼀場 BGP 劫持的攻防⼤賽。這場⽐賽⼀共有 N ⽀隊伍參加，每⽀隊伍會維護⼀台伺服器，之後主辦⽅每次會把⼀個封包丟給⼀個伺服器，並指定他要傳向哪個伺服器。接著每台伺服器會根據他的路由表，選擇⼀個伺服器傳遞封包，而參賽者要做的就是盡可能讓不相關的封包經過⾃⼰，從而破解其中的資訊，而封包的傳遞⽅和接收⽅則要負責保護傳遞的路徑不要被攻擊。作為全國資安第⼀把交椅，翔哥也有關注全國資訊安全能⼒競賽模擬賽，但是翔哥真的太強了，這種⽐賽的勝敗他並不放在⼼上，他關⼼的是有沒有可能⼤家都享受到⽐賽的過程。雖然傳遞的路徑會根據路由表以及接收者而異，可是這對翔哥來說是 a piece of cake。他已經預測出了 M 個封包潛在被劫持的⽅式。根據封包傳遞的性質，這些路徑必定不會讓封包在數個隊伍之間循環傳遞。

現在，翔哥想知道是否存在⼀種 BGP 劫持的狀況，使得封包會經過每⽀隊伍恰好⼀次。

輸入說明 :

輸⼊的第⼀⾏包含兩個⾮負整數 N 、M ，代表全國資訊安全能⼒競賽模擬賽⼀共有 N 個隊伍參加，且有 M 個可能的封包劫持狀況。接下來的 M ⾏，每⾏包含兩個正整數 si、ti，代表第 si 個隊伍拿到的封包有可能被第 ti 個隊伍劫持。保證不存在⼀種劫持路徑使得⼀個封包可以在數個隊伍之間循環傳遞。

輸出說明 :

如果存在⼀種劫持封包的⽅式，使得每個隊伍會接⼿那個封包恰好⼀次，請輸出 N 個正整數於⼀⾏，代表封包可以依序經過哪些隊伍的伺服器，否則請輸出 −1。如果有很多種封包傳遞路徑都滿⾜條件，輸出任意⼀個都可以獲得 Accepted。

範例輸入 1 :

範例輸出 1 :

3 5 1 2 4

範例輸入 2 :

範例輸出 2 :

-1

題解 :

剛看到題目可能會以為是漢米頓路徑。然而實際上仔細閱讀後應該會發現，他保證圖是一個DAG，也因此可以主張一個貪婪法性質，必須由入度為0的點開始。並且，因為入度為0的點沒有進入的邊，所以兩個或以上的點入度為0時保證沒有路徑。如下圖

BGP_1 必定是依照 1 -> 2 -> 3 的順序拔點，而下圖是一個沒有路徑的範例

BGP_2 因為拔完1之後有兩個點入度為0，所以無解。

實作程式碼如下(因為比賽所以含有比較多巨集和一些其他的簡化技巧，我會在使用時加上註解)

#include<bits/stdc++.h>
using namespace std;

//縮短long long變數宣告以及常用常數
using ll=long long;
const ll MOD=1e9+7;
const ll INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const ll N=1000010;
const ll M=1010;
const long double PI=3.14159265358979;

//巨集(競賽縮短程式碼技巧)
#define ALL(v) v.begin(),v.end();
#define siz(v) ((int)v.size())
#define F first
#define S second
#define EB emplace_back
#define PB pop_back
#define EF emplace_front
#define PF pop_front
#define EE emplace
#define rs resize
#define MP make_pair

template<typename T> using prior=priority_queue<T>;
template<typename T> using Prior=priority_queue<T,vector<T>,greater<T>>;
template<typename T> using Stack=stack<T,vector<T>>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;

//N=1000010
vector<int> g[N];
//ind存入度
int ind[N];
int n,m;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>n>>m;
    for(int i=0;i<m;++i){
        int f,t;
        cin>>f>>t;
//      EB -> emplace_back
        g[f].EB(t);
        ind[t]++;
    }

    queue<int> bfs;

    int ctind=0;
    for(int i=1;i<=n;++i){
        if(ind[i]==0){
            ctind++;
//          EE -> emplace
            bfs.EE(i);
//          兩個或以上的點入度為0
            if(ctind>1){
                cout<<-1;
                return 0;
            }
        }
    }

    vector<int> ans;
    while(!bfs.empty()){
        int n=bfs.front();
        bfs.pop();
//      EB -> emplace_back
        ans.EB(n);

        int ctind=0;
        for(auto i:g[n]){
            ind[i]--;
            if(ind[i]==0){
                ctind++;
//              EE -> emplace
                bfs.EE(i);
//              兩個或以上的點入度為0
                if(ctind>1){
                    cout<<-1;
                    return 0;
                }
            }
        }
    }

    for(auto i:ans){
        cout<<i<<" ";
    }
}

前言