Description
FGD開辦了一家電話公司。他雇用了N個職員，給了每個職員一部手機。每個職員的手機里都存儲有一些同事的 電話號碼。由于FGD的公司規模不斷擴大，舊的辦公樓已經顯得十分狹窄，FGD決定將公司遷至一些新的辦公樓。FG D希望職員被安置在盡量多的辦公樓當中，這樣對于每個職員來說都會有一個相對更好的工作環境。但是，為了聯 系方便起見，如果兩個職員被安置在兩個不同的辦公樓之內，他們必須擁有彼此的電話號碼。 Input
第一行包含兩個整數N（2<=N<=100000）和M（1<=M<=2000000）。職員被依次編號為1,2,……,N.以下M行，每 行包含兩個正數A和B(1<=A Output
包含兩行。第一行包含一個數S，表示FGD最多可以將職員安置進的辦公樓數。第二行包含S個從小到大排列的 數，每個數后面接一個空格，表示每個辦公樓里安排的職員數。 Sample Input 7 16
1 3
1 4
1 5
2 3
3 4
4 5
4 7
4 6
5 6
6 7
2 4
2 7
2 5
3 5
3 7
1 7
Sample Output 3
1 2 4 HINT
FGD可以將職員4安排進一號辦公樓，職員5和職員7安排進2號辦公樓，其他人進3號辦公樓
解題方法： 首先注意到，我們直接求這個問題很難求解，所以我們考慮轉化，那么可以轉化成什么呢？ 轉化成補圖聯通塊的個數， 這個是在床上突然想到的，補圖就是完全圖去掉這個圖剩下的部分，那么補圖的聯通塊之間有邊恰恰對應原圖一個集合無邊，補圖連通塊之間無邊，恰恰對應原圖不在同一集合的點存在邊。我們知道這個結論并不能解決這個問題，因為補圖顯然是稠密圖，我們直接遍歷邊用并查集維護的話顯然是（n^2），顯然是要T的，然后我也卡住了，翻翻大牛的題解，找打了一種非常NB的方法，是OI的ysq大牛提出的，叫做鏈表加BFS的強優化，具體是這樣的：我們先把所有的節點掛鏈，然后再把鏈表上的一個節點入隊，遍歷其在原圖上相鄰的點并做上標記，那么這時沒有打上標記的點在補圖上和當前節點一定有邊相連因而一定在同一個聯通塊中，所以再把這些沒有打上標記的點入隊，并且在鏈表中除去，繼續這個過程，直到隊列為空時這個聯通塊就找出來了，再取鏈表上還存在的點入隊尋找一個新的聯通塊，直到刪掉所有點為止，復雜度降為了O(n + m)。然后這個題目就可以完美解決了，完結撒花。。
#include <bits/stdc++.h>using namespace std;const int maxn = 100010;const int maxm = 2000010;int n, m, edgecnt, head[maxn];struct edge{int v, nxt; } E[maxm*2];struct link{int PRe, nxt; }L[maxn];void del(int x){ L[L[x].pre].nxt = L[x].nxt; L[L[x].nxt].pre = L[x].pre;}void init(){ memset(head, -1, sizeof(head)); edgecnt = 0;}void addedge(int u, int v){ E[edgecnt].v = v, E[edgecnt].nxt = head[u], head[u] = edgecnt++;}bool vis1[maxn], vis2[maxn]; //vis1標記相鄰點，vis2標記在隊列的存在狀態int scc[maxn], scccnt;void bfs(){ queue <int> q; memset(vis1, 0, sizeof(vis1)); memset(vis2, 0, sizeof(vis2)); while(L[0].nxt){//還存在節點 int now = L[0].nxt, curscc = 1; del(now); q.push(now); vis2[now] = 1; while(!q.empty()){ int u = q.front(); q.pop(); for(int i = head[u]; ~i; i = E[i].nxt) vis1[E[i].v] = 1; for(int i = L[0].nxt; i; i = L[i].nxt){ if(!vis1[i] && !vis2[i]){ vis2[i] = 1; q.push(i); curscc++; del(i); } } for(int i = head[u]; ~i; i = E[i].nxt) vis1[E[i].v] = 0; //一定取消相鄰節點的標記 } scc[++scccnt] = curscc; }}int main(){ init(); scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++){ int u, v; scanf("%d%d", &u, &v); addedge(u, v); addedge(v, u); } for(int i = 1; i <= n; i++){ L[i-1].nxt = i; L[i].pre = i - 1; } L[n].nxt = 0; bfs(); sort(scc + 1, scc + scccnt + 1); printf("%d/n", scccnt); for(int i = 1; i < scccnt; i++) printf("%d ", scc[i]); printf("%d", scc[scccnt]); return 0;}新聞熱點
疑難解答
