强连通分量

模板（强联通分量个数+缩点）

#include<iostream>

#include<cstdio>

#define MAXn 100000

#define MAXm 2000000

using namespace std;

int dfn[MAXn],low[MAXn],head[MAXm],st[MAXn],belong[MAXn];

bool in_st[MAXn];

int ans,n,m,num,s_num,cnt,group_num;

struct node{

    int to,pre;

}e[MAXm];

void Insert(int from,int to){

    e[++num].pre=head[from];

    e[num].to=to;

    head[from]=num;

}

void group(int u){

    cnt++;st[++s_num]=u;dfn[u]=low[u]=cnt;in_st[u]=;

    for(int i=head[u];i;i=e[i].pre){

        int v=e[i].to;

        if(!dfn[v]){

            group(v);

            if(low[v]<low[u])low[u]=low[v];

        }

        else if(dfn[v]<low[u])

            if(in_st[v])

            low[u]=dfn[v];

    }

    if(dfn[u]==low[u]){

        group_num++;

        while(st[s_num]!=u){

            in_st[st[s_num]]=;

            belong[st[s_num]]=group_num;

            s_num--;

        }

        in_st[u]=;s_num--;

        belong[u]=group_num;

    }

}

int main(){

    freopen("Tarjan_group.txt","r",stdin);

    scanf("%d%d",&n,&m);int x,y;

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

        scanf("%d%d",&x,&y);

        Insert(x,y);

    }

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

        if(!dfn[i])group(i);

    }

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

        printf("%d ",belong[i]);

    }printf("\n%d",group_num);

}

Tarjan_group模板

例题

poj3114  Countries in War

跑一边强连通分量，搞出缩点，求缩点间的最短路

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define maxm 250010

#define maxn 510

int head[maxm],dfn[maxn],low[maxn],st[maxn],belong[maxn],blong[maxn][maxn];

int n,m,num,order,cnt,s_num,num_g,dis[maxn][maxn];

int nw[][];

bool in_st[maxn];

struct node{

    int to,v,pre;

}e[maxm];

void Insert(int from,int to,int v){

    e[++num].to=to;

    e[num].pre=head[from];

    e[num].v=v;

    head[from]=num;

}

void group(int u){

    cnt++;dfn[u]=low[u]=cnt;st[++s_num]=u;in_st[u]=;

    for(int i=head[u];i;i=e[i].pre){

        int v=e[i].to;

        if(!dfn[v]){

            group(v);

            if(low[v]<low[u])low[u]=low[v];

        }

        else if(dfn[v]<low[u])

            if(in_st[v])low[u]=dfn[v];

    }

    if(low[u]==dfn[u]){

        num_g++;

        while(st[s_num]!=u){

            blong[num_g][++blong[num_g][]]=st[s_num];

            belong[st[s_num]]=num_g;

            in_st[st[s_num]]=;

            s_num--;

        }belong[u]=num_g;

        blong[num_g][++blong[num_g][]]=u;

        in_st[u]=;s_num--;

    }

}

int main(){

    freopen("Tarjan_group.txt","r",stdin);

    int nm,nn;

    while(){

        cin>>n>>m;

        if(n==&&m==)break;

        memset(dfn,,sizeof(dfn));

        memset(head,,sizeof(head));

        memset(low,,sizeof(low));

        memset(st,,sizeof(st));

        memset(e,,sizeof(e));

        memset(belong,,sizeof(belong));

        memset(blong,,sizeof(blong));

        num_g=;s_num=;cnt=;

        int x,y,z;

        memset(nw,/,sizeof(nw));

        memset(dis,/,sizeof(dis));

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

            scanf("%d%d%d",&x,&y,&z);

            Insert(x,y,z);

            nw[x][y]=z;

        }

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

            if(!dfn[i])group(i);

        }

        /*for(int i=1;i<=n;i++)

        cout<<belong[i]<<' ';cout<<endl<<endl;*/

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

            dis[i][i]=;

            nw[i][i]=;

        }

        for(int k=;k<=n;k++){

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

                for(int j=;j<=n;j++){

                    if(i!=j&&i!=k&&k!=j)

                    nw[i][j]=min(nw[i][j],nw[i][k]+nw[k][j]);

                }

            }

        }

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

            for(int j=;j<=num_g;j++){//找到两个缩点

                if(i!=j){

                    for(int k=;k<=blong[i][];k++){

                        for(int l=;l<=blong[j][];l++){

                            if(k!=l)

                            dis[i][j]=min(dis[i][j],nw[blong[i][k]][blong[j][l]]);

                        }

                    }

                }

            }

        }

        int p;

        scanf("%d",&p);

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

            scanf("%d%d",&x,&y);

            if(dis[belong[x]][belong[y]]>=)cout<<"Nao e possivel entregar a carta"<<endl;

            else cout<<dis[belong[x]][belong[y]]<<endl;

        }

    }

}

TLE

#include<cstring>

#include<cstdio>

#include<iostream>

#define Max 505

using namespace std;

int map[Max][Max];

struct Edge{

    int to,w;

    int next;

}edge[Max * Max];

int head[Max],tol;

void add(int u,int v,int w){

    edge[tol].to=v;

    edge[tol].w=w;

    edge[tol].next=head[u];

    head[u]=tol++;

}

int dfn[Max],low[Max],Stack[Max],belong[Max];

int bcnt,time,top,instack[Max];

void tarjan(int u){

    dfn[u]=low[u]=++time;

    Stack[top++]=u;

    instack[u]=true;

    for(int i=head[u];i!=-;i=edge[i].next){

        int v=edge[i].to;

        if(!dfn[v]){

            tarjan(v);

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

        }

        else{

            if( instack[v])

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

        }

    }

    int v;

    if(low[u] == dfn[u]){

        bcnt++;

        do{

            v = Stack[--top];

            instack[v] = false;

            belong[v] = bcnt;

        }while(u != v);

    }

}

int main(){

    int n,m;

    int v,u,w;

    while(~scanf("%d%d", &n,&m)){

        if(!n && !m) break;

        memset(head,-,sizeof(head));

        tol=;

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

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            add(u,v,w);

        }

        memset(dfn,,sizeof(dfn));

        memset(low,,sizeof(low));

        top=time=bcnt=;

        for(int i=;i<=n;i++)

            if(!dfn[i])

              tarjan(i);

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

              for(int j=;j<=n;j++)

                if(i==j)

                map[i][j]=;

              else map[i][j]=0x3f3f3f3f;

          }  

          for(u=;u<=n;u++)  {

              for(int j=head[u];j!=-;j=edge[j].next)  {

                  v=edge[j].to;

                  w=edge[j].w;

                  if(belong[u]!=belong[v])

                    map[belong[u]][belong[v]]=min(map[belong[u]][belong[v]],w);

              }

          }

          for(int k=;k<=bcnt;k++){

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

                  for(int j=;j<=bcnt;j++)

                    if(map[i][j]>map[i][k]+map[k][j])

                      map[i][j]=map[i][k]+map[k][j];

              }

          }

          int t;

          scanf("%d",&t);

          while(t--){

              scanf("%d%d",&u,&v);

              if(map[belong[u]][belong[v]] == 0x3f3f3f3f)

                printf("Nao e possivel entregar a carta\n");

              else

              printf("%d\n",map[belong[u]][belong[v]]);

          }

          printf("\n");

    }

    return ;

}

AC

poj1236Network of Schools

题意：一个包含1-n号学校的网络，每个学校有个软件分发列表，当学校拿到软件时会把软件分发给列表里的学校。 
问1：一个新软件出现时初始化情况至少需要给多少个学校才能让它到达整个网络？ 
问2：至少需要添加多少个名单才能使从任意一个学校开始分发都能充满整个网络？

也就是： 
—给定一个有向图，求：

1) 至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点

2) 至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶点

DAG上面有多少个入度为0的顶点，问题1的答案就是多少 
在DAG上要加几条边，才能使得DAG变成强连通的，问题2的答案就是多少

加边的方法：假定有 n 个入度为0的点，m个出度为0的点，max(m,n)就是第二个问题的解

#include<iostream>

#include<cstdio>

using namespace std;

#define maxn 110

#define maxm (maxn*(maxn - 1)/2)

int n,num,cnt,num_g,num_in0,num_out0;

int in[maxn],out[maxn],head[maxm],belong[maxn],dfn[maxn],low[maxn],st[maxn],s_num;

int blong[maxn][maxn],nmp[maxn][maxn];

bool s_in[maxn],vis[maxn][maxn];

struct node{

    int to,pre;

}e[maxm];

void Insert(int from,int to){

    e[++num].pre=head[from];

    e[num].to=to;

    head[from]=num;

}

void group(int u){

    cnt++;dfn[u]=low[u]=cnt;st[++s_num]=u;s_in[u]=;

    for(int i=head[u];i;i=e[i].pre){

        int v=e[i].to;

        if(dfn[v]==){

            group(v);

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

        }

        else if(dfn[v]){

            /*if(s_in[v])*/low[u]=min(low[u],dfn[v]);

        }

    }

    if(low[u]==dfn[u]){

        num_g++;

        while(st[s_num]!=u){

            s_in[st[s_num]]=;

            belong[st[s_num]]=num_g;

            blong[num_g][++blong[num_g][]]=st[s_num];

            s_num--;

        }

        s_num--;belong[u]=num_g;

        blong[num_g][++blong[num_g][]]=u;

    }

}

int main(){

    freopen("1236.txt","r",stdin);

    scanf("%d",&n);int a;

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

        while(){

            scanf("%d",&a);

            if(a==)break;

            Insert(i,a);

        }

    }

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

        if(dfn[i]==)group(i);

    }

    /*for(int i=1;i<=num_g;i++){//枚举每个缩点

        for(int j=1;j<=blong[i][0];j++){//枚举缩点里的每个点

            int u=i;

            for(int k=head[blong[i][j]];k;k=e[k].pre){

                int v=belong[e[k].to];

                if(vis[u][v]==0&&v!=u){

                    vis[u][v]=1;in[v]++;out[u]++;

                }

            }

        }

    }*/

    for(int u=;u<=n;u++){

        for(int i=head[u];i;i=e[i].pre){

            int v=e[i].to;

            if(belong[u]!=belong[v]){

                in[belong[v]]++;

                out[belong[u]]++;

            }

        }

    }

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

        if(in[i]==)num_in0++;

        if(out[i]==)num_out0++;

    }

    cout<<num_in0<<endl;

    if(num_g==)cout<<;

    else cout<<max(num_in0,num_out0);

    return ;

}

wa

最新文章

  1. 蓄水池（Reservoir_sampling）抽样算法简记
  2. ie6、7下 text-indent 问题
  3. vs2010通过添加资源文件，修改win32创建的窗口
  4. 在sqlServer中把数据导出为insert脚本
  5. hdu 1527 取石子游戏（Wythoff Game）
  6. sqlserver任务导出Excle
  7. Head First设计模式之访问者模式
  8. ssm maven spring AOP读写分离
  9. JavaScript将小写金额转换成大写
  10. pat1061-1070
  11. vbox的桥接网络
  12. [ZZ] 麻省理工( MIT)大神解说数学体系
  13. u-boot移植（十二）---代码修改---支持DM9000网卡
  14. 黄聪：php精度计算问题
  15. C# 将 Stream 写入文件
  16. css3动画（animation）效果1-漂浮的白云
  17. Struts2学习-Ioc学习
  18. python基础===tkinter学习链接
  19. 初识Python、PyCharm、Anaconda与tensorflow
  20. Android无线测试之—UiAutomator UiObject API介绍六

热门文章

  1. PYTHON调用C接口(基于Ctypes)实现stein算法最大公约数的计算
  2. c# &amp;与&amp;&amp; 和 |与||的区别（转载）
  3. pkg-config设置
  4. 国际电话号码的区号mysql数据表
  5. Custom Database Integration Guide
  6. Oracle学习笔记_05_ 一个创建表空间、创建用户、授权的完整过程
  7. codeforces 569B B. Inventory(水题)
  8. kettle 设置变量
  9. AtCoder Beginner Contest 100 2018/06/16
  10. 「LuoguP1725」琪露诺（dp 单调队列