POJ1523：SPF——题解

这题明显就是求割点然后求割完之后的强连通分量的个数。

割点都会求，怎么求割完的分量个数呢？

我们可以通过万能的并查集啊！（具体做法看代码吧，方法不好叙述）

这样我们查割点它所连的点一共隶属于几个集合即可。

（PS：读入方式很恶心，同时请注意快速读入）

#include<stack>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

inline int read(){

    int x=,w=;char ch=;

    while(ch<''||ch>''){if(ch=='-')w=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

    return x*w;

}

const int maxn=;

bool dis[maxn][maxn];

bool cut[];

int dfn[maxn];

int low[maxn];

int fa[maxn];

int from[maxn];

int t;

int big[maxn];

int to[maxn];

int find(int a){

    if(a==fa[a])return a;

    return fa[a]=find(fa[a]);

}

void tarjan(int u,int f){

    bool tong[maxn]={};

    from[u]=f;

    t++;

    dfn[u]=t;

    low[u]=t;

    to[t]=u;

    for(int v=;v<=maxn;v++){

    if(dis[u][v]){

        if(!dfn[v]){

        tarjan(v,u);

        low[u]=min(low[u],low[v]);

        }else if(f!=v){

        low[u]=min(low[u],dfn[v]);

        }

    }

    fa[find(u)]=find(to[low[u]]);

    }

    for(int v=;v<=maxn;v++){

    if(dis[u][v]){

        if(!tong[find(v)]){

        tong[find(v)]=;

        big[u]++;

        }

    }

    }

    return;

}

int main(){

    int u,v;

    int cnt=;

    bool smg=;

    while(){

    int u=read();

    if(!u&&!smg)break;

    smg=;

    if(!u){

        for(int i=;i<=maxn;i++)fa[i]=i;

        tarjan(,);

        int rootson=;

        bool ok=;

        for(int i=;i<=maxn;i++){

        int v=from[i];

        if(v==)rootson++;

        else{

            if(low[i]>=dfn[v]&&low[i]&&dfn[i]){

            cut[v]=;

            ok=;

            }

        }

        }

        if(rootson>=){

        cut[]=;

        ok=;

        }

        cnt++;

        printf("Network #%d\n",cnt);

        if(ok==){

        printf("  No SPF nodes\n");

        }else{

        for(int i=;i<=maxn;i++){

            if(cut[i])printf("  SPF node %d leaves %d subnets\n",i,big[i]);

        }

        }

        printf("\n");

        memset(cut,,sizeof(cut));

        memset(dfn,,sizeof(dfn));

        memset(low,,sizeof(low));

        memset(fa,,sizeof(fa));

        memset(from,,sizeof(from));

        memset(dis,,sizeof(dis));

        memset(big,,sizeof(big));

        memset(to,,sizeof(to));

        t=;

        smg=;

        continue;

    }

    int v=read();

    dis[u][v]=dis[v][u]=;

    }

    return ;

}