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 阅读(380)
评论(0) 编辑 收藏 引用 所属分类:
acm_icpc