题目链接“点击打开链接

判断割点的个数

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         const int N = 210; const int maxn = 500; const int maxm = 21010; const int inf = 1e8; #define MIN INT_MIN #define MAX 1e6 #define LL long long #define init(a) memset(a,0,sizeof(a)) #define FOR(i,a,b) for(int i = a;i
        
         b)?(a):(b) #define min(a,b) (a>b)?(b):(a) using namespace std; int DFN[maxn],low[maxn],head[maxn]; bool dian[maxn]; int bianhao,n,bnum,root,vis[maxn]; int gedian[maxn],ge; struct edge { int v,next; }edge[maxm]; void add(int u,int v) { edge[bnum].v=v; edge[bnum].next=head[u]; head[u]=bnum++; } void tarjan(int u,int father)//判定割点 { int son=0; vis[u]=1;//标记 DFN[u]=low[u]=bianhao++; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(vis[v]==1 && v!=father) low[u]=min(low[u],DFN[v]); if(vis[v]==0) { tarjan(v,u); son++; low[u]=min(low[u],low[v]); if((u==root && son>1 ) || (u!=root && DFN[u]<=low[v]))//判定割点的条件 { dian[u]=1; } } } vis[u]=2;//去掉 } void initt() { memset(head,-1,sizeof(head)); init(DFN);init(low); init(vis);init(dian); bnum=0;bianhao = 1;//ge = 0; } int main() { int a,b; while(scanf("%d",&n),n) { initt(); while(scanf("%d",&a),a) { while(getchar()!='\n') { scanf("%d",&b); add(a,b); add(b,a); } } root=1; tarjan(1,-1); int ans = 0; FOR(i,1,n+1) { if(dian[i]!=0) { ans++; // gedian[ge++] = i; } } cout<