图论-有向图的连通性模板题（hdu1296）（hdu1827）

1.强连通分量：
强连通分量可以理解为边数最少的情况下是一个环。
这里写了一个模板题用的是tarjan算法，当然还有其他算法。
tarjan算法的关键其实还是对于num数组和low数组的使用
然后可以用栈来分离不同的ssc
感觉跟双边连通分量有异曲同工之妙

第一题hdu1296

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#define maxn 20010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int n,m;
vector < vector<int> > maps;
int low[maxn];
int num[maxn];
int stacks[maxn],ssc[maxn];
int dfsnum=0,top,cnt;
void init(){
    memset(low,0,sizeof(low));
    memset(num,0,sizeof(num));
    memset(ssc,0,sizeof(ssc));
    dfsnum=0;
    top=0;
    cnt=0;
}
void dfs(int u){
    stacks[top++]=u;
    low[u]=num[u]=++dfsnum;
    for(int i=0;i<maps[u].size();i++){
        int v=maps[u][i];
        if(!num[v]){
            dfs(v);
            low[u]=min(low[v],low[u]);
        }
        else if(!ssc[v])  low[u]=min(low[u],num[v]);  //处理回退边
    }
    if(low[u]==num[u]){   //栈底的点是ssc的祖先，low=num值
        cnt++;
        while(true){
            int v=stacks[--top];
            ssc[v]=cnt;
            if(u==v)  break;
        }
    }
}

void tarjan(){
    init();
    for(int i=1;i<=n;i++)   //因为最少便的情况下是一个环，所以说从哪个点开始走，都可以回到原始点
        if(!num[i])  dfs(i);
}



int main()
{
    while(scanf("%d%d",&n,&m)&&n){
        init();
        maps.clear();
        maps.resize(10010);
        for(int i=0;i<m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            maps[x].push_back(y);
        }
        tarjan();
        if(cnt>1)  printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

第二题hdu1827
这个还是先用tarjan算法来求有多少个强连通分量，然后我们再用缩点的思想把一个强连通量当一个点来看，因为要最少的人，相当于找入度0的人来打电话。

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#define maxn 2010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int n,m;
vector < vector<int> > maps;
int low[maxn];
int num[maxn];
int stacks[maxn],ssc[maxn];
int dfsnum=0,top,cnt;
int price[maxn];
int cost[maxn];
int degree[maxn];
void init(){
    memset(low,0,sizeof(low));
    memset(num,0,sizeof(num));
    memset(ssc,0,sizeof(ssc));
    memset(degree,0,sizeof(degree));
    memset(cost,MaxN,sizeof(cost));
    dfsnum=0;
    top=0;
    cnt=0;
}
void dfs(int u){
    stacks[top++]=u;
    low[u]=num[u]=++dfsnum;
    for(int i=0;i<maps[u].size();i++){
        int v=maps[u][i];
        if(!num[v]){
            dfs(v);
            low[u]=min(low[v],low[u]);
        }
        else if(!ssc[v])  low[u]=min(low[u],num[v]);
    }
    if(low[u]==num[u]){
        cnt++;
        while(true){
            int v=stacks[--top];
            ssc[v]=cnt;
            cost[cnt]=min(cost[cnt],price[v]);
            if(u==v)  break;
        }
    }
}
void tarjan(){
    for(int i=1;i<=n;i++)
        if(!num[i]){
            dfs(i);
        }
    for(int i=1;i<=n;i++){
        for(int f=0;f<maps[i].size();f++){
            if(ssc[i]!=ssc[maps[i][f]])  degree[ssc[maps[i][f]]]++;
        }
    }
    int ans1=0,ans2=0;

    //for(int i=1;i<=n;i++) cout<<degree[i]<<" ";

    for(int i=1;i<=cnt;i++){
        if(degree[i]==0)  ans2+=cost[i],ans1++;
    }
    printf("%d %d\n",ans1,ans2);
}



int main()
{
    while(scanf("%d%d",&n,&m)!=EOF){
        init();
        maps.clear();
        maps.resize(1010);
        for(int i=1;i<=n;i++)  scanf("%d",&price[i]);

        for(int i=0;i<m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            maps[x].push_back(y);
        }
        tarjan();
    }
    return 0;
}