這里先給出結(jié)論:
　　對于非根節(jié)點的割點,它能分割圖為cut[i]+1個連通分量;對于根節(jié)點割點,它能分割圖為cut[i]個連通分量
　　至于為什么,找了好久沒找到答案...
F - SPF
題意:
求刪點割點后,割點所割連通分量數(shù)

#include <cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<set>
#include<algorithm>
#include<iterator>
using namespace std;
const int MAXN=1010;
const int MAXE=200010;
struct Node
{
    int to,next;
}edge[MAXE];
int head[MAXN],cnt;
void addEdge(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int cutCnt[MAXN],low[MAXN],dfn[MAXN],clocks;
set<int> cut;
void DFS(int u,int e)
{
    low[u]=dfn[u]=++clocks;
    int child=0;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        if(i==(e^1)) continue;
        int v=edge[i].to;
        if(dfn[v]==0)
        {
            child++;
            DFS(v,i);
            low[u]=min(low[v],low[u]);
            if(low[v]>=dfn[u])
            {
                cut.insert(u);
                cutCnt[u]++;
            }
        }
        else if(dfn[v]<dfn[u])
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(e<0&&child==1)
    {
        set<int>::iterator it=cut.find(u);
        if(it!=cut.end()) cut.erase(it);
    }
    else if(e!=-1) cutCnt[u]++;//非根節(jié)點
}
void work(int n)
{
    memset(dfn,0,sizeof(dfn));
    memset(cutCnt,0,sizeof(cutCnt));
    clocks=0;
    cut.clear();
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0)
        {
            DFS(i,-1);
        }
    }
}
int main()
{
    int n,m,a,b,cas=1,maxv;
    while(true)
    {
        maxv=0;
        scanf("%d",&a);
        maxv=max(maxv,a);
        if(a==0) break;
        scanf("%d",&b);
        maxv=max(maxv,b);
        memset(head,-1,sizeof(head));
        cnt=0;
        addEdge(a,b);
        addEdge(b,a);
        while(true)
        {
            scanf("%d",&a);
            maxv=max(maxv,a);
            if(a==0) break;
            scanf("%d",&b);
            maxv=max(maxv,b);
            addEdge(a,b);
            addEdge(b,a);
        }
        work(maxv);
        printf("Network #%d\n",cas++);
        if(cut.size()==0) printf("  No SPF nodes\n");
        else
        {
            for(set<int>::iterator it=cut.begin();it!=cut.end();it++)
            {
                printf("  SPF node %d leaves %d subnets\n",*it,cutCnt[*it]);
            }
        }
        printf("\n");
    }
}

其實一開始不知道有上面那個結(jié)論,所以我最初的做法是先求出所有的割點和點連通分量,然后再對每個割點求從該割點出發(fā)的每條邊的另一個端點的不同的點連通分量數(shù)。

#include <cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<set>
#include<algorithm>
#include<iterator>
using namespace std;
const int MAXN=1010;
const int MAXE=200010;
struct Node
{
    int to,next;
}edge[MAXE];
int head[MAXN],cnt;
void addEdge(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
struct Edge
{
    int u,v;
    Edge(){}
    Edge(int u,int v):u(u),v(v){}
};
int cutCnt[MAXN],low[MAXN],dfn[MAXN],clocks,bccno[MAXN],bcc_cnt;
int vis[MAXN];
stack<Edge> sta;
set<int> cut;
void DFS(int u,int e)
{
    low[u]=dfn[u]=++clocks;
    int child=0;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        if(i==(e^1)) continue;
        int v=edge[i].to;
        Edge ee(u,v);
        if(dfn[v]==0)
        {
            sta.push(ee);
            child++;
            DFS(v,i);
            low[u]=min(low[v],low[u]);
            if(low[v]>=dfn[u])
            {
                cut.insert(u);
                bcc_cnt++;
                while(true)
                {
                    Edge x=sta.top();
                    sta.pop();
                    if(bccno[x.u]!=bcc_cnt) {bccno[x.u]=bcc_cnt;}
                    if(bccno[x.v]!=bcc_cnt) {bccno[x.v]=bcc_cnt;}
                    if(x.u==u&&x.v==v) break;
                }
            }
        }
        else if(dfn[v]<dfn[u])
        {
            sta.push(ee);
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(e<0&&child==1)
    {
        set<int>::iterator it=cut.find(u);
        if(it!=cut.end()) cut.erase(it);
    }
}
void work(int n)
{
    memset(dfn,0,sizeof(dfn));
    clocks=bcc_cnt=0;
    memset(bccno,0,sizeof(bccno));
    while(!sta.empty()) sta.pop();
    cut.clear();
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0)
        {
            DFS(i,-1);
        }
    }
    int sum;
    for(set<int>::iterator it=cut.begin();it!=cut.end();it++)
    {
        int u=*it;
        sum=0;
        memset(vis,0,sizeof(vis));
        for(int j=head[u];j!=-1;j=edge[j].next)
        {
            int v=edge[j].to;
            if(vis[bccno[v]]==0)
            {
                vis[bccno[v]]=1;
                sum++;
            }
        }
        cutCnt[u]=sum;
    }
}
int main()
{
    int n,m,a,b,cas=1,maxv;
    while(true)
    {
        maxv=0;
        scanf("%d",&a);
        maxv=max(maxv,a);
        if(a==0) break;
        scanf("%d",&b);
        maxv=max(maxv,b);
        memset(head,-1,sizeof(head));
        cnt=0;
        addEdge(a,b);
        addEdge(b,a);
        while(true)
        {
            scanf("%d",&a);
            maxv=max(maxv,a);
            if(a==0) break;
            scanf("%d",&b);
            maxv=max(maxv,b);
            addEdge(a,b);
            addEdge(b,a);
        }
        work(maxv);
        printf("Network #%d\n",cas++);
        if(cut.size()==0) printf("  No SPF nodes\n");
        else
        {
            for(set<int>::iterator it=cut.begin();it!=cut.end();it++)
            {
                printf("  SPF node %d leaves %d subnets\n",*it,cutCnt[*it]);
            }
        }
        printf("\n");
    }
}