强连通专题

用户1624346

发布于 2018-04-17 08:14:25

97900

代码可运行

文章被收录于专栏：calmoundcalmound

运行总次数：0

代码可运行

POJ 2762 Going from u to v or from v to u?

题意：判断该图的任意两点是否可达

分析：tarjan后进行缩点，缩点后再建图，判断该图是否为单链式图形（只有一个叶结点）判断能到达该点的节点个数是否等于bcnt

#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
using namespace std;
const int MN=2011;
vector<int>edge[MN];
vector<int>SCC[MN];
stack<int>s;

int low[MN],dfn[MN];
int instack[MN],stap[MN];
int belong[MN];
int num[MN];
int ind[MN];
int tp,p;
int bcnt;

void tarjan(int x)
{
    low[x]=dfn[x]=++tp;
    stap[++p]=x;
    instack[x]=1;
    for(int i=0;i<edge[x].size();i++)
    {
        int v=edge[x][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            if(low[x]>low[v])
               low[x]=low[v];
        }
        else if(instack[v] && dfn[v]<low[x])
               low[x]=dfn[v];
    }
    if(low[x]==dfn[x])
    {
        int top;
        do
        {
            top=stap[p];
            belong[top]=bcnt;
            instack[top]=0;
            p--;
        }while(x!=top);
        bcnt++;
    }
}

void topsort()
{
    memset(num,0,sizeof(num));
    int i,u,v;
    while(!s.empty())
        s.pop();
    for(int i=0;i<bcnt;i++)
        if(ind[i]==0)
        {
            s.push(i);
            num[i]++;
        }
    while(!s.empty())
    {
        u=s.top();
        s.pop();
        for(int i=0;i<SCC[u].size();i++)
        {
            v=SCC[u][i];
            if(--ind[v]==0)
            {
                s.push(v);
                num[v]=num[u]+1;
            }
        }
    }
}

int main()
{
    int T,n,m,i,a,b,j;
    scanf("%d",&T);
    while(T--)
    {
        bcnt=tp=p=0;
        scanf("%d%d",&n,&m);
        memset(dfn,-1,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(instack,0,sizeof(instack));
        memset(belong,0,sizeof(belong));
        memset(ind,0,sizeof(ind));
        for(i=1;i<=n;i++)
        {
            edge[i].clear();
            SCC[i].clear();
        }
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            edge[a].push_back(b);
        }
        for(i=1;i<=n;i++)
        {
            if(dfn[i]==-1) tarjan(i);
        }
        for(i=1;i<=n;i++)
        {
            for(j=0;j<edge[i].size();j++)
            {
                int x=belong[i];
                int y=belong[edge[i][j]];
                if(x!=y)
                {
                     SCC[x].push_back(y);
                     ind[y]++;
                }
            }
        }
        topsort();
        int ans=-1;
        for(i=0;i<bcnt;i++)
        {
            ans=max(ans,num[i]);
        }
       // printf("%d\n",ans);
        if(bcnt==ans) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

POJ 2553 Popular Cows

题意：若牛A崇拜牛B，牛B崇拜牛C，则牛A崇拜牛C，问总共有多少只牛受到其他所有牛的崇拜

分析：若有环存在，则该环里的所有牛都互相崇拜，则可将环看成是一个点，后再构图，若想存在某个点的牛收到其他所有牛的崇拜，则该图必定是单链式图形（只有一个叶结点） tarjan缩点反向建图，然后只有一个入度为0

#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
using namespace std;
const int MN=11000;
vector<int>SCC[MN];
vector<int>edge[MN];
stack<int>s;

int low[MN],dfn[MN];
int instack[MN],stap[MN];
int belong[MN];
int num[MN];
int ind[MN];
int sum[MN];
int tp,p;
int bcnt;
int n,m;
int cnt;
int pos;

void tarjan(int x)
{
    low[x]=dfn[x]=++tp;
    stap[++p]=x;
    instack[x]=1;
    for(int i=0;i<edge[x].size();i++)
    {
        int v=edge[x][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            if(low[x]>low[v])
               low[x]=low[v];
        }
        else if(instack[v] && dfn[v]<low[x])
             low[x]=dfn[v];
    }
    if(low[x]==dfn[x])
    {
        int top;
        do
        {
            top=stap[p];
            belong[top]=bcnt;
            sum[bcnt]++;
            instack[top]=0;
            p--;
        }while(x!=top);
        bcnt++;
    }
}

void topsort()
{
    int u,v;
    stack<int>s;
    memset(num,0,sizeof(num));
    for(int i=0;i<bcnt;i++)
    {
        if(ind[i]==0)
        {
            s.push(i);
            pos=i;
            cnt++;
        }
    }
}

int main()
{
    int i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(dfn,-1,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(instack,0,sizeof(instack));
        memset(belong,0,sizeof(belong));
        memset(ind,0,sizeof(ind));
        memset(sum,0,sizeof(sum));
        bcnt=tp=p=0;
        for(i=1;i<=n;i++)
        {
            edge[i].clear();
            SCC[i].clear();
        }
        for(i=0;i<m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            edge[a].push_back(b);
        }
        for(i=1;i<=n;i++)
        {
            if(dfn[i]==-1) tarjan(i);
        }
        for(i=1;i<=n;i++)
        {
            for(j=0;j<edge[i].size();j++)
            {
                int x=belong[i];
                int y=belong[edge[i][j]];
                if(x!=y)
                {
                    SCC[y].push_back(x);
                    ind[x]++;
                }
            }
        }
        int ans=0;
        cnt=0;
        topsort();
        if(cnt==1) printf("%d\n",sum[pos]);
        else printf("0\n");
    }
    return 0;
}

POJ 2553 The Bottom of a Graph

题意：求出所有sink集合，sink集合的定义若v可达w，则w必定也可达v，求出所有的叶结点便可而头节点不可以的原因是若v属于V，w不属于V，而v可达w，但是w不可达v，所以不可以至于叶结点呢，v可达w，其中w必定都属于V集合

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
const int MN=5010;
vector<int>SCC[MN];
vector<int>edge[MN];

int low[MN],dfn[MN];
int instack[MN],stap[MN];
int belong[MN];
int num[MN];
int ind[MN];
int rem[MN];
int tp,p;
int bcnt;
int n,m;
int cas;

void tarjan(int x)
{
    low[x]=dfn[x]=++tp;
    stap[++p]=x;
    instack[x]=1;
    for(int i=0; i<edge[x].size(); i++)
    {
        int v=edge[x][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            if(low[x]>low[v])
                low[x]=low[v];
        }
        else if(instack[v] && dfn[v]<low[x])
            low[x]=dfn[v];
    }
    if(low[x]==dfn[x])
    {
        int top;
        do
        {
            top=stap[p];
            belong[top]=bcnt;
            instack[top]=0;
            p--;
        }
        while(x!=top);
        bcnt++;
    }
}

void topsort()
{
    for(int i=0; i<bcnt; i++)
    {
        if(ind[i]==0)
        {
            for(int j=1; j<=n; j++)
            {
                if(belong[j]==i) rem[cas++]=j;
            }
        }
    }
}

bool cmp(int a,int b)
{
    return a<b;
}

int main()
{
    int i,w,v,j;
    while(scanf("%d",&n) && n)
    {
        scanf("%d",&m);
        tp=p=bcnt=cas=0;
        memset(dfn,-1,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(instack,0,sizeof(instack));
        memset(belong,0,sizeof(belong));
        memset(ind,0,sizeof(ind));
        for(i=0; i<=n; i++)
        {
            edge[i].clear();
            SCC[i].clear();
        }
        for(i=0; i<m; i++)
        {
            scanf("%d%d",&w,&v);
            edge[w].push_back(v);
        }
        for(i=1; i<=n; i++)
        {
            if(dfn[i]==-1) tarjan(i);
        }
        for(i=1; i<=n; i++)
        {
            for(j=0; j<edge[i].size(); j++)
            {
                int x=belong[i];
                int y=belong[edge[i][j]];
                if(x!=y)
                {
                    SCC[y].push_back(x);
                    ind[x]++;
                }
            }
        }
        topsort();
        sort(rem,rem+cas,cmp);
        printf("%d",rem[0]);
        for(i=1; i<cas; i++)
        {
            printf(" %d",rem[i]);
        }
        printf("\n");

    }
    return 0;
}

POJ 1523 SPF

题意：找出割点，且将割点拿掉后，存在几个连通分量分析：构建一棵dfs树，序列dfn[i]为深度优先数，表示dfs时访问i节点的序号，low[i]表示从i节点出发能访问到的最小的深度优先数。当且仅当节点u满足如下两个条件之一时，u为割点： 1.u为dfs树的根，且u至少有两个子节点。 2.u不是dfs树的根，至少存在一个节点v是u的子节点，且low[v]>=dfn[u]。若u为割点，记subnets[u]为u的子节点数，则去掉u后，图被分成subnets[u]+1个部分（每个子节点的部分和u的祖先的部分），若u为dfs树的根，则分成subnets[u]个部分（根节点没有祖先）。 以上全部算法均在dfs过程中完成。

割点模板

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MN=1111;

struct Edge
{
    int to,next;
} edge[MN<<2];
int dfn[MN];
int low[MN];
int head[MN<<2];
int subnet[MN];
int E;
int tp;
int root;
int vis[MN];

void Init()
{
    memset(dfn,-1,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(head,-1,sizeof(head));
    memset(subnet,0,sizeof(subnet));
    memset(vis,0,sizeof(vis));
    E=tp=0;
}

void Add(int a,int b)
{
    edge[E].to=b;
    edge[E].next=head[a];
    head[a]=E++;
}

void tarjan(int u,int fa){  //割点模板
    int son=0;
    vis[u]=1;
    dfn[u]=low[u]=++tp;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if(vis[v]==1 && v!=fa)
            low[u]=min(low[u],dfn[v]);
        if(!vis[v]){
            tarjan(v,u);
            son++;
            low[u]=min(low[u],low[v]);
            if((u==root && son>1) || (u!=root && dfn[u]<=low[v]))
                subnet[u]++;   //cut[u] 表示u这个点割边数
        }
    }
    vis[u]=2;
}

int main()
{
    int i,cas=1,n,a,b,nodes;
    while(scanf("%d",&n) && n)
    {
        nodes=n;
        Init();
        scanf("%d",&b);
        Add(n,b);
        Add(b,n);
        while(scanf("%d",&a) && a)
        {
            scanf("%d",&b);
            if(nodes<a) nodes=a;
            if(nodes<b) nodes=b;
            Add(a,b);
            Add(b,a);
        }
        for(i=1; i<=nodes; i++)
        {
            if(dfn[i]==-1)
            {root=i;
                tarjan(i,-1);
                
            }
        }
        int flag=0;
        printf("Network #%d\n",cas++);
        for(i=1; i<=nodes; i++)
        {
            if(subnet[i]>=1)
            {
                flag=1;
                printf("  SPF node %d leaves %d subnets\n",i,subnet[i]+1);
            }
        }
        if(flag==0) printf("  No SPF nodes\n");
        puts("");
    }
    return 0;
}