Network UVA - 315 kuangbin帶你飛 專題九 連通圖 圖論 tarjan

題意

求割點

tarjan 模闆題

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_V 110
#define MAX_E 10010
#define mem(a) memset((a),0,sizeof(a))
struct edge{
  int to;
  int next;
};
edge es[MAX_E];
int head[MAX_V],len;
int V;
int dfn[MAX_V],low[MAX_V];
int ord;
int instack[MAX_V];
int vcut[MAX_V];
int root;
void addedge(int from,int to)
{
  es[len].to = to;
  es[len].next = head[from];
  head[from] = len++;
}
void tarjan(int u,int fa){
  dfn[u] = low[u] = ++ord;
  instack[u] = ;
  int cnt =;
  for (int i = head[u];i != -;i = es[i].next){
    int v = es[i].to;
    if (v == fa){
      continue;
    }
    if (dfn[v] == -){
      tarjan(v,u);
      cnt++;
      if (low[u] > low[v]){
        low[u] = low[v];
      }
      if (root == u && cnt > ){
        vcut[u] = ;
      } else if (root != u && low[v] >= dfn[u]){
        vcut[u] = ;
      }
    } else if (instack[v]){
      if(dfn[v] < low[u]){
        low[u] = dfn[v];
      }||
    }
  }
}
void init(){
  len = ord = ;
  mem(low);
  mem(instack);
  mem(vcut);
  memset(dfn,-,sizeof dfn);
  memset(head,-,sizeof head);
}
void solve(){
  root = ;
  tarjan(,-);
  int ans = ;
  for (int i = ;i<=V;i++){
    if (vcut[i]) ans++;
  }
  printf("%d\n",ans);
}
int main()
{
  int u,v;
  while(~scanf("%d",&V),V){
    init();
    while (scanf("%d", &u), u)  {
      while (getchar() != '\n')  {
        scanf("%d", &v);
        addedge (u, v);
        addedge (v, u);
      }
    }
    solve();

  }
    return ;
}