定义

割点：删掉该点后，原连通图分裂为多个子图；

桥：删掉该边后，原连通图分裂为多个子图；

求割点：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int maxn=150000+10;int dfn[maxn],low[maxn];bool iscut[maxn];vector
         
          pic[maxn];int dfs_clock=0;void tarjan(int x,int fa){	int child=0;	dfn[x]=low[x]=++dfs_clock;	for (int i=0;i
          
           =dfn[x]) iscut[x]=true; } else low[x]=min(low[x],dfn[y]); } if (fa==-1&&child<=1) iscut[x]=false;}int main(){ int n,m; scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); pic[x].push_back(y); pic[y].push_back(x); } memset(dfn,0,sizeof(dfn)); memset(iscut,0,sizeof(iscut)); for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i,-1); int cnt=0; for (int i=1;i<=n;i++) if (iscut[i]) cnt++; printf("%d\n",cnt); return 0;}
          
         
        
       
      
     

　　求桥:

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int maxn=100;vector
         
          pic[maxn];int dfn[maxn],low[maxn];int dfs_clock=0;void tarjan(int x,int fa){	dfn[x]=low[x]=++dfs_clock;	for (int i=0;i