SPF

 

题意：无向图，求割顶以及去掉该割顶后有几个连通分量。

去掉一个割顶后，从割顶dfs遍历整张图，每扫一个连通分量计数器加1

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 const int maxv=1010; 6 int n; 7 struct Edge{ 8     int v,nex; 9 }e[maxv*maxv<<1];10 int head[maxv];11 int cnt=0;12 void init(){13     memset(head,-1,sizeof(head));14     cnt=0;15     n=0;16 }17 void add(int u,int v){18     e[cnt].v=v;19     e[cnt].nex=head[u];20     head[u]=cnt++;21 }22 23 int pre[maxv],iscut[maxv],dfsk;24 25 int dfs(int u,int id){26     int lowu=pre[u]=++dfsk;27     int child=0;28     for(int i=head[u];i!=-1;i=e[i].nex){29         if(i==(id^1)) continue;30         int v=e[i].v;31         if(!pre[v]){32             child++;33             int lowv=dfs(v,i);34             lowu=min(lowu,lowv);35             if(lowv>=pre[u]) iscut[u]=1;36         }37         else if(pre[v]