uestc 方老师炸弹

转自http://www.cnblogs.com/whatbeg/p/3765625.html

Tarjan算法。

1.若u为根，且度大于1，则为割点

2.若u不为根，如果low[v]>=dfn[u],则u为割点（出现重边时可能导致等号，要判重边）

3.若low[v]>dfn[u],则边(u,v)为桥(封死在子树内），不操作。

求割点时，枚举所有与当前点u相连的点v：

1.是重边：忽略

2.是树边： Tarjan(v)，更新low[u]=min(low[u],low[v]); 子树个数cnt+1.如果low[v] >= dfn[u]，说明是割点，割点数+1

3.是回边：更新low[u] = min(low[u],dfn[v])，因为此时v是u的祖先。

关于Tarjan求割点可见：http://hi.baidu.com/lydrainbowcat/item/f8a5ac223e092b52c28d591c

代码：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<string>
  6 #include<queue>
  7 #include<algorithm>
  8 #include<map>
  9 #include<iomanip>
 10 #include<climits>
 11 #include<string.h>
 12 #include<cmath>
 13 #include<stdlib.h>
 14 #include<vector>
 15 #include<stack>
 16 using namespace std;
 17 #define INF 1000000007
 18 #define MAXN 40010
 19 #define Mod 1000007
 20 #define N 10007
 21 #define NN 30
 22 #define sigma_size 3
 23 const int maxn = 6e5 + 10;
 24 using namespace std;
 25 typedef long long LL;
 26 
 27 struct CUT{
 28     int v, num;
 29     bool operator<(const CUT a) const{
 30         if (num == a.num)
 31             return v < a.v;
 32         return num > a.num;
 33     }
 34 }cut[N];
 35 vector<int> G[N];
 36 int vis[N], dfn[N], low[N], Time;
 37 int n, m, k;
 38 int i, j, u, v;
 39 
 40 void init()
 41 {
 42     Time = 0;
 43     for (int i = 0; i <= n; ++i) {
 44         G[i].clear();
 45         cut[i].v = i;
 46         cut[i].num = 1;
 47     }
 48     cut[0].num = 0;
 49     memset(dfn, 0, sizeof(dfn));
 50     memset(low, 0, sizeof(low));
 51     memset(vis, 0, sizeof(vis));
 52 }
 53 
 54 
 55 void Tarjan(int u, int fa)
 56 {
 57     low[u] = dfn[u] = ++Time;
 58     int cnt = 0;
 59     vis[u] = 1;
 60     int flag = 1;
 61     for (int i = 0; i<G[u].size(); i++)
 62     {
 63         int v = G[u][i];
 64         if (v == fa && flag)  //重边
 65         {
 66             flag = 0;
 67             continue;
 68         }
 69         if (!vis[v])    //树边
 70         {
 71             Tarjan(v, u);
 72             cnt++;
 73             low[u] = min(low[u], low[v]);
 74             if (low[v] >= dfn[u])
 75                 cut[u].num++;
 76         }
 77         else if (vis[v] == 1)   //回边
 78             low[u] = min(low[u], dfn[v]);
 79     }
 80     if (fa == -1 && cnt == 1)  //为根且度数为1，不是割点
 81         cut[u].num = 1;
 82     vis[u] = 2;
 83     return;
 84 }
 85 
 86 int main()
 87 {
 88     while (cin >> n >> m >> k) {
 89         init();
 90         for (i = 0; i < m; ++i) {
 91             cin >> u >> v;
 92             G[u].push_back(v);
 93             G[v].push_back(u);
 94         }
 95         Tarjan(0,-1);
 96         sort(cut, cut + n);
 97         for (i = 0; i<k; i++)
 98             printf("%d %d
", cut[i].v, cut[i].num);
 99         printf("
");
100     }
101     //system("pause");
102     return 0;
103 }