[割点][强连通分量] POJ1523 SPF

这题略坑。。。输入的可以是不连续的点，我一开始都从1开始dfs，WA了n发发现数据里可能没1这个点。。。GG

求割点的话本身倒是很裸，但是还要求出生成的子集个数，也是试了各种奇怪的方法。。。。后来发现把low[v]>=pre[u]的子节点v的数量记下来就可以了，至于证明。。。直觉证明法吧

#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=2e3+5;

vectorG[maxn];
int scc,siz[maxn],s[maxn],belong[maxn],top,clock,isfuck[maxn],low[maxn],pre[maxn],flag=0;
int dfs(int u,int fa)
{
    int lowu=pre[u]=++clock;
    int child=0;
    for (int i=0; i=pre[u])
            {
                isfuck[u]++;
            }
        }
        else if(pre[v]ans;
int main()
{
    int cnt=0;
    int u,v,mn,root;

    while(~scanf("%d",&u)&&u)
    {
        root=u;
        ans.clear();
        mn=scc=top=clock=flag=0;
        memset(G,0,sizeof(G));
        memset(pre,0, sizeof(pre));
        memset(isfuck,0,sizeof(isfuck));
        //memset(belong,0,sizeof(belong));
        cnt++;
        scanf("%d",&v);
        G[u].push_back(v);
        G[v].push_back(u);
        mn=max(u,v);
        while(scanf("%d",&u)&&u)
        {
            scanf("%d",&v);
            G[u].push_back(v);
            G[v].push_back(u);
            mn=max(u,v);
        }

        printf("Network #%d\n",cnt);
        dfs(root,-1);
        if(isfuck[root]!=0)
            isfuck[root]--;
        for (int i=1; i<=mn; i++)
        {

            if(isfuck[i])
            {
                flag=1;
                printf("  SPF node %d leaves %d subnets\n",i,isfuck[i]+1);
            }
        }
        if(!flag)
            printf("  No SPF nodes\n");
        puts("");
    }
    return 0;
}