MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
如果n == 1 结果就是0 //wa一次
如果m == 0 结果就是n - 1 //wa一次

其他的情况 :

看看割点去掉后,能有几个联通分量,也就是割点有几个儿子。 这个就是去掉个点后增加的分量个数。


#include <stdio.h>
#include 
<string.h>
const int N = 10001;
const int M = 20001;
struct e{
    
int v;
    e
* next;
};
*link[N], edge[M * 2];
int m, n, son[N], rootdegree, el, b[N], bb[N], time;
bool judge[N];
int min(int a, int b){
    
return a > b ? b : a;
}
void dfs(int u, int root){
    e 
*= link[u];int i, v;bool c = false;
    b[u] 
= bb[u] = time++;judge[u] = true;
    
while(l){
        v 
= l->v;
        
if(!judge[v]){
            dfs(v, root);
            
if(u == root){
                rootdegree
++;
                
if(rootdegree >= 2) son[u]++;
            }
            
else{
                bb[u] 
= min(bb[u], bb[v]);
                
if(bb[v] >= b[u])son[u]++;
            }
        }
        
else bb[u] = min(bb[u], b[v]);
        l 
= l->next;
    }
}
int main(){
    freopen(
"2299.in""r", stdin);
    freopen(
"2299.out""w", stdout);
    
int i, j, u, v, fl, ans;
    
while(scanf("%d%d"&n, &m), n || m){
        
for(i = 0; i < n; i++){
            b[i] 
= bb[i] = judge[i] = 0;son[i] = 1;link[i] = NULL;
        }el 
= rootdegree = fl = 0;
        
for(i = 0; i < m; i++){
            scanf(
"%d%d"&u, &v);
            edge[el].v 
= v;edge[el].next = link[u];link[u] = &edge[el++];
            edge[el].v 
= u;edge[el].next = link[v];link[v] = &edge[el++];
        }
        
if(n == 1){
            puts(
"0");continue;
        }
        
if(m == 0){
            printf(
"%d\n", n - 1);continue;
        }
        
for(i = 0; i < n; i++){
            
if(!judge[i]){
                rootdegree 
= time = 0;dfs(i, i);fl++;
            }
        }ans 
= 1;
        
for(i = 0; i < n; i++){
            
if(son[i] > ans)ans = son[i];
        }printf(
"%d\n", ans + fl - 1);
    }
    
return 0;
}

posted on 2009-10-08 17:49 memorygarden 阅读(367) 评论(0)  编辑 收藏 引用 所属分类: 报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理