08合肥網賽某題。
http://poj.org/problem?id=3697題意是問在N個點的完全圖(N<=10,000)中刪掉M(M<=1,000,000)條邊后, 還有多少個點與頂點1連通(頂點編號從1開始).
暴力BFS+HASH+各種WS優化的方法很多, 但是出題人原意應該是O(M)的做法吧... 下面是我YY出來的O(M)的做法.
只考慮這M條待刪邊, 能得到什么信息呢? 可以先從點1入手. 掃一遍與1鄰接的點, 那么剩下沒被掃到的點肯定與1是連通的. 而被掃到的點是"有可能"與1不連通. 所以就把那些肯定與1連通的點做標記. 從這些確定連通的點中任選一個u, 再掃描它的所有鄰接點. 這之后, 如果一個點一共被掃了2次, 那么它才"有可能"與1不連通, 其它少于2次的點肯定與1連通, 因為它或者與1連通, 或者與u連通, 而u是已知與1連通的. 這樣再拿出一個已經確定連通的點, 掃描它的鄰接點, 把被掃過次數<3的又標記為已連通......
經過上面的YY, 算法基本上就出來了:
把已知肯定與1連通的點集稱為S, 剩下不確定的為T. 一開始, S中只有1這一個點, 其它點都在T中. 每個點有個計數器, 記錄自己被掃了多少次.
1) 從S中取出一個沒處理過的點, 把它標記為已處理, 并遍歷它的所有鄰接點, 被遍歷到的點的計數器都+1.
2) T中所有"計數<S中已處理點個數"的, 都可以確定是連通的, 把它們從T中刪除, 加入S中.
3) 重復1), 直到S中所有點都處理完.
這時, S中的點就是與1連通的, T中剩下的就是不連通的.
復雜度分析:
讀入邊和掃描邊都是O(M)的.
S集可以用隊列維護, 總共O(N).
T集的維護: 每一輪都要掃一遍當前的T, 把所有計數小的刪掉, 放進S中. 這樣, 這一步的總復雜度就是O(sigma(T)), 會不會到達O(N^2)呢? 實際上是不會的. 因為一條邊最多只會使一個頂點的計數+1, 因此每一輪還剩在T中的點數不會超過這一輪遍歷過的邊數. 這樣, 所有回合的sigma(T)就肯定不會超過總邊數. 因此這里總共也是O(M)的. 嚴格來說算上第1輪有N-1個點, 也是O(M+N).
這樣總的復雜度就是O(M)了.
不過這個算法讀入用scanf時, g++跑了1000+ms, 改成getchar才到200+ms的. 不知道排前面的神們是不是有更NB的算法.
代碼:
1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7
8 const int MAXN = 10010;
9 const int MAXM = 1000010;
10
11 struct Edge {
12 int v, next;
13 }edg[MAXM*2];
14 int ecnt, gg[MAXN];
15 bool yes[MAXN];
16 int que[MAXN], pq, sq, cnt[MAXN], vt[MAXN], nt;
17 int N, M;
18
19 inline int getnextint()
20 {
21 int r = 0;
22 char c;
23 while(!isdigit(c=getchar()));
24 do{
25 r = r*10 + c-'0';
26 } while(isdigit(c=getchar()));
27 return r;
28 }
29
30 inline void addedge(int u , int v)
31 {
32 edg[ecnt].v = v; edg[ecnt].next = gg[u], gg[u] = ecnt++;
33 edg[ecnt].v = u; edg[ecnt].next = gg[v], gg[v] = ecnt++;
34 }
35
36 int main()
37 {
38 int cas = 0;
39 while(~scanf("%d%d", &N, &M) && !(N==0 && M==0)){
40
41 ecnt = 0;
42 for(int i = 0; i < N; i++){
43 gg[i] = -1;
44 yes[i] = i==0 ? true : false;
45 cnt[i] = 0;
46 vt[i] = i+1;
47 }
48 nt = N-1;
49
50 for(int i = 0; i < M; i++){
51 int u = getnextint();
52 int v = getnextint();
53 addedge(--u, --v);
54 }
55
56 pq = sq = 0;
57 que[sq++] = 0;
58 yes[0] = true;
59
60 while(pq != sq) {
61 int u = que[pq++];
62 for(int e = gg[u]; e >= 0; e = edg[e].next) {
63 if(!yes[edg[e].v])
64 cnt[edg[e].v]++;
65 }
66 for(int i = 0; i < nt; i++) {
67 while(i < nt && cnt[vt[i]] < pq) {
68 yes[vt[i]] = true;
69 que[sq++] = vt[i];
70 if(i < --nt)
71 vt[i] = vt[nt];
72 }
73 }
74 }
75 printf("Case %d: %d\n", ++cas, sq-1);
76
77 }
78 return 0;
79 }
posted on 2011-08-15 03:06
wolf5x 閱讀(399)
評論(0) 編輯 收藏 引用 所屬分類:
acm_icpc