poj 2135 最小费用最大流
hdu 3416 最短路+最大流

poj 2186 强连通分支

scturtle posted @ 2010年9月05日 01:34 in algorithm , 1948 阅读

tarjan 485MS

原理: 在任何深度优先搜索中,同一强连通分量内的所有顶点均在同一棵深度优先搜索树中。也就是说,强连通分量一定是有向图的某个深搜树子树。
定义dfn(u)为节点u的时间戳,low(u)为节点u或u的子树能追溯到的最小的栈中节点的dfn值。当dfs回溯时发现dfn(u)==low(u),则u是分量子树的根,从u到栈顶为一个连通分支里的。

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef vector<int>::iterator it;
#define maxn 10001
int inline min(int a,int b){return a<b?a:b;}
vector<int> g[maxn];
int dfn[maxn],low[maxn],stack[maxn];
int idx,top;
bool instack[maxn];
int sc,f[maxn],cnt[maxn];

void tarjan(int u)
{
    dfn[u]=low[u]=++idx;
    stack[top++]=u; instack[u]=1;
    for(it v=g[u].begin();v!=g[u].end();++v)
        if(!dfn[*v])//not visited
            tarjan(*v),low[u]=min(low[u],low[*v]);
        else if(instack[*v])
            low[u]=min(low[u],dfn[*v]);
    if(dfn[u]==low[u])//find root
    {
        ++sc;cnt[sc]=0;
        do { f[stack[--top]]=sc; cnt[sc]++;
            instack[stack[top]]=0; 
        } while(u!=stack[top]);
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
    }
    idx=top=sc=0;
    memset(dfn,0,sizeof(dfn));
    memset(instack,0,sizeof(instack));
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    //for(int i=1;i<=n;i++) printf("%d ",f[i]);

    //缩点
    int out[sc+1];memset(out,0,sizeof(out));
    for(u=1;u<=n;u++)
        for(it v=g[u].begin();v!=g[u].end();++v)
            if(f[u]!=f[*v]) out[f[u]]++;
    int count=0,ans;
    for(int i=1;i<=sc && count<2;i++)
        if(out[i]==0) count++,ans=i;
    if(count==1) printf("%d\n",cnt[ans]);
    else puts("0");
}

kosaraju 360MS

步骤:
1. dfs原图得到拓扑序。
2. 按照拓扑序dfs反图,每个dfs树中的顶点都是一个连通分支里的。

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define maxn 10001
typedef vector<int>::iterator it;
vector<int> g[maxn],gr[maxn];
int t,gs[maxn];//toposort of g
int fs,f[maxn];//result of SCC
bool vit[maxn];

void dfs(int v)
{
    vit[v]=true;
    for(it w=g[v].begin();w!=g[v].end();++w)
        if(!vit[*w]) dfs(*w);
    gs[t--]=v;//记录拓扑顺序(finish时间的反序)
}

void rdfs(int v)
{
    vit[v]=true; f[v]=fs;
    for(it w=gr[v].begin();w!=gr[v].end();++w)
        if(!vit[*w]) rdfs(*w);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,m,v,w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        g[i].clear(), gr[i].clear();
    while(m--)
    {
        scanf("%d%d",&v,&w);
        g[v].push_back(w);
        gr[w].push_back(v);
    }
    //正向
    memset(vit,false,sizeof(vit));
    t=n;
    for(int i=1;i<=n;i++)
        if(!vit[i]) dfs(i);
    //拓扑序
    //for(int i=1;i<=n;i++)
        //printf("%d ",gs[i]);
    //puts("");
    //逆向
    memset(vit,false,sizeof(vit));
    fs=0;
    for(int i=1;i<=n;i++)//拓扑序遍历反图
        if(!vit[gs[i]]) ++fs, rdfs(gs[i]);
    //输出每个点所属的强联通号 1~fs
    //for(int i=1;i<=n;i++)
        //printf("%d ",f[i]);

    //for poj 2186 缩点
    int out[fs+1],num[fs+1];
    memset(out,0,sizeof(out));
    memset(num,0,sizeof(num));
    for(int v=1;v<=n;v++)
    {
        num[f[v]]++;
        for(it w=g[v].begin();w!=g[v].end();++w)
            if(f[v]!=f[*w]) out[f[v]]++;
    }
    int cnt=0,ans;
    for(int i=1;i<=fs && cnt<2;i++)
        if(out[i]==0) cnt++,ans=i;
    if(cnt==1) printf("%d\n",num[ans]);
    else puts("0");
}

gabow 532MS

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstdlib>
#define maxn 10001
using namespace std;
int n,m;
vector<int> g[maxn];
int pre[maxn],path[maxn],sc[maxn],s[maxn],ct[maxn];
int cnt0,cnt1,p,top;
bool outis0[maxn];

void scDfs(int w)
{
    int v,i;
    pre[w]=cnt0++;
    s[top++]=w;path[p++]=w;
    for(i=0;i<g[w].size();i++)
    {
        v=g[w][i];
        if(pre[v]==-1) scDfs(v);
        else if(sc[v]==-1)
            while(pre[path[p-1]]>pre[v]) p--;
    }
    if(path[p-1]!=w) return; else p--;
    do sc[s[--top]]=cnt1; while(s[top]!=w);
    cnt1++;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int v,w,i,j;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++) g[i].clear();
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&v,&w);
        g[v-1].push_back(w-1);
    }

    p=cnt0=cnt1=top=0;
    for(int i=0;i<n;i++)
        sc[i]=pre[i]=-1;

    for(int i=0;i<n;i++)
        if(sc[i]==-1) scDfs(i);

    //缩点
    for(i=0;i<cnt1;i++) {outis0[i]=1;ct[i]=0;}
    for(i=0;i<n;i++)
    {
        ct[sc[i]]++;
        for(j=0;j<g[i].size();j++)
            if(sc[i]!=sc[g[i][j]]) outis0[sc[i]]=0;
    }
    int index,count=0;
    for(i=0;i<cnt1;i++)
        if(outis0[i]) {index=i;count++;}
    if(count==1) printf("%d\n",ct[index]);
    else printf("0\n");
    return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter