POJ_2117 Elcctricity (tarjan 求割点)-白红宇

POJ_2117 Elcctricity (tarjan 求割点)

阅读量：6200 次

发布时间：2019-06-21

本文共 2136 字，大约阅读时间需要 7 分钟。

　　题意：求一个图中删掉一个结点所得到的连通块数量最大。

　　思路：设一个结点u，如果u是根结点（图可能是不连通的，所以可能有多个根结点）则删掉u所增加的连通块数为 SUM(u的子结点) - 1；

如果u是非根结点，v是u的子结点，则删掉u所增加的连通块数为 SUM(u->v为割边，既u是到v的割点)；

渣代码：

View Code

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5  6 using namespace std;  7  8 const int N = 10005;  9 const int M = 1000005; 10 11 struct node {
    12     int to; 13     int next; 14 } g[M]; 15 16 int head[N], num[N]; 17 int dfn[N], low[N]; 18 int t, ind, Rcnt, ans; 19 bool vis[N]; 20 21 void init() {
    22     memset(head, 0, sizeof(head)); 23     memset(num, 0, sizeof(num)); 24     memset(dfn, 0, sizeof(dfn)); 25     memset(low, 0, sizeof(low)); 26     memset(vis, 0, sizeof(vis)); 27 28     t = 1; ind = Rcnt = 0; 29 } 30 31 void add(int u, int v) {
    32     g[t].to = v; g[t].next = head[u]; head[u] = t++; 33 } 34 35 void tarjan(int u, int r) {
    36     int v, i; 37     dfn[u] = low[u] = ++ind; 38     for(i = head[u]; i; i = g[i].next) {
    39         v = g[i].to; 40         if(!dfn[v]) {
    41             tarjan(v, r); 42             if(u == r) Rcnt ++; 43             else {
    44                 low[u] = min(low[u], low[v]); 45                 if(low[v] >= dfn[u])    num[u]++; 46             } 47 48         } else {
    49             low[u] = min(low[u], dfn[v]); 50         } 51     } 52     ans = max(ans, num[u]); 53 } 54 55 int main() {
    56     //freopen("data.in", "r", stdin); 57 58     int n, m, u, v; 59     int i, sum; 60     while(scanf("%d%d", &n, &m), n || m) {
    61         if(m == 0) { printf("%d\n", n-1); continue; } 62         init(); 63         for(i = 1; i <= m; i++) {
    64             scanf("%d%d", &u, &v); 65             add(u, v); 66             add(v, u); 67         } 68         sum = 0, ans = 0; 69         for(i = 0; i < n; i++) {
    70             if(!dfn[i]) {
    71                 Rcnt = 0; 72                 tarjan(i, i); 73                 num[i] = Rcnt-1; 74                 ans = max(num[i], ans); 75                 sum++; 76             } 77         } 78         printf("%d\n", ans + sum); 79     } 80     return 0; 81 }