封鎖陽光大學 題目描述

曹是一只愛刷街的老曹，暑假期間，他每天都歡快地在陽光大學的校園里刷街。河蟹看到歡快的曹，感到不爽。河蟹決定封鎖陽光大學，不讓曹刷街。

10年積累的成都網站設計、成都網站建設經驗，可以快速應對客戶對網站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網絡服務。我雖然不認識你，你也不認識我。但先做網站后付款的網站建設流程，更有長子免費網站建設讓你可以放心的選擇與我們合作。

陽光大學的校園是一張由 n n n 個點構成的無向圖， n n n 個點之間由 m m m 條道路連接。每只河蟹可以對一個點進行封鎖，當某個點被封鎖后，與這個點相連的道路就被封鎖了，曹就無法在這些道路上刷街了。非常悲劇的一點是，河蟹是一種不和諧的生物，當兩只河蟹封鎖了相鄰的兩個點時，他們會發(fā)生沖突。

詢問：最少需要多少只河蟹，可以封鎖所有道路并且不發(fā)生沖突。

輸入格式

第一行兩個正整數，表示節(jié)點數和邊數。
接下來 m m m 行，每行兩個整數 u , v u,v u,v，表示點 u u u 到點 v v v 之間有道路相連。

輸出格式

僅一行如果河蟹無法封鎖所有道路，則輸出Impossible，否則輸出一個整數，表示最少需要多少只河蟹。

樣例 #1 樣例輸入 #1

3 3
1 2
1 3
2 3

樣例輸出 #1

Impossible

樣例 #2 樣例輸入 #2

3 2
1 2
2 3

樣例輸出 #2

1

提示

【數據規(guī)?！?br />對于 100 % 100\% 100% 的數據， 1 ≤ n ≤ 1 0 4 1\le n \le 10^4 1≤n≤104， 1 ≤ m ≤ 1 0 5 1\le m \le 10^5 1≤m≤105，保證沒有重邊。

思路： 可在圖中用1表示有河蟹占據，-1表示無河蟹占據。當所有路徑都被封鎖時，一定會滿足以下兩個條件：
①一條道路的兩端不能同時是1或-1
②每個點都會被標記為1或-1
而如果出現了不能封鎖的情況，那么一定是在某一個點處出現了道路兩端的標記相同的情況。
因此，可用廣度優(yōu)先搜索遍歷這個無向圖，將起始點標記為1，然后將搜索到的下一個點標記為上一個點的相反數（即-1），如果下一個點已經被標記過且與上一個點的標記相同，則說明不能封鎖全部道路。
注意，全部的點標記完之后可能會出現標記為1的點多于標記為-1的點的情況，因此需要取兩種標記點數量的較小值。同時，因為可能會出現多個圖（某些點與其他的點不連通），因此需要把每個點嘗試作為遍歷起點，若這個點沒被訪問過則以這個點為起始點進行遍歷。

代碼：

#includeusing namespace std;
int n, m, dot[10005], ans = 0;
bool vis[10005];
vectorvec[10005];
queueq;
int main(){cin >>n >>m;
    for(int i = 1; i<= m; i++){int x, y;
        cin >>x >>y;
        vec[x].push_back(y), vec[y].push_back(x);
    }
    for(int i = 1; i<= n; i++){int a = 0, b = 0;
        if(!vis[i] && !vec[i].empty()){q.push(i);
            dot[i] = 1;
            while(!q.empty()){int now = q.front();
                q.pop();
                if(dot[now] == 1) a++;
                else if(dot[now] == -1) b++;
                vis[now] = true;
                for(int i = 0; i< vec[now].size(); i++){int to = vec[now][i];
                    if(vis[to]){if(dot[to] == dot[now]){cout<< "Impossible";
                            return 0;
                        }
                    }
                    else{q.push(to);
                        dot[to] = -dot[now];
                    }
                }
            }
        }
        ans += min(a, b);
    }
    cout<< ans;
    return 0;
}

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網頁標題：【C++】洛谷P1330封鎖陽光大學-創(chuàng)新互聯(lián)
URL鏈接：http://weahome.cn/article/esdop.html