首页 > 其他 > 详细

连通图练习总结

时间：2015-04-06 12:44:42      阅读：99      评论：0      收藏：0      [点我收藏+]

连通图是图论基于联通的一个概念，在ACM中针对图论的考察一部分是也是基于连通图。针对这类问题的解题基本思路就是先求出对应的连通分量（有向图的强连通，无向图的双连通）对图进行简化，然后再结合其他算法计算。

1. POJ 3180 The Cow Prom

这个题如果能理解题目的话，怎么做就很明显了，能形成一个可以转圈的小群，就相当于一个强连通分量，需要注意的就是这个小群不可以只有一头牛。

#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

#pragma comment(linker, "/STACK:1024000000,1024000000")

#define     IT              iterator
#define     PB(x)           push_back(x)
#define     CLR(a,b)        memset(a,b,sizeof(a))

using namespace std;

typedef     long long               ll;
typedef     unsigned long long      ull;
typedef     vector<int>             vint;
typedef     vector<ll>              vll;
typedef     vector<ull>             vull;
typedef     set<int>                sint;
typedef     set<ull>                sull;

const int maxn = 10000 + 5;
vint G[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int> S;
int a[maxn];

void init(int n) {
    for (int i = 0; i <= n; i++) G[i].clear();
}

void dfs(int u) {
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!pre[v]) {
            dfs(v);
            lowlink[u] = min(lowlink[u],lowlink[v]);
        }
        else if (!sccno[v]) {
            lowlink[u] = min(lowlink[u],pre[v]);
        }
    }
    if (lowlink[u] == pre[u]) {
        scc_cnt++;
        while (1) {
            int x = S.top();
            S.pop();
            sccno[x] = scc_cnt;
            if (x == u) break;
        }
    }
}

void find_scc(int n) {
    dfs_clock = scc_cnt = 0;
    CLR(sccno,0);
    CLR(pre,0);
    for (int i = 1; i <= n; i++) {
        if (!pre[i]) dfs(i);
    }
}

int cnt[maxn];

int main() {
    int n,m;
    //freopen("data.in","r",stdin);
    while (cin>>n>>m) {
        init(n);
        for (int i = 0; i < m; i++) {
            int a,b;
            scanf("%d%d",&a,&b);
            G[a].PB(b);
        }
        //for (int i = 0; i <= scc_cnt; i++) new_g[i].clear();
        find_scc(n);
        for (int i = 1; i <= n; i++) {
            cnt[sccno[i]]++;
        }
        int ans = 0;
        /*cout<<scc_cnt<<endl;
        for (int i = 1; i <= scc_cnt; i++) {
            for (int j = 0; j < new_g[i].size(); j++) {
                cout<<i<<" "<<new_g[i][j].from<<" "<<new_g[i][j].cost<<endl;
            }
        }*/
        for (int i = 1; i <= scc_cnt; i++) {
            if (cnt[i] > 1) ans++;
        }
        cout<<ans<<endl;
    }
}

 2. POJ 1236 Network of Schools

最开始对于图的处理同样也是需要用强连通缩点重新构图，然后针对两个任务，第一个很好理解就是入度为0的强连通个数，第二个问题需要小小想一下，欲将整个图变成一个强连通，那么就相当于把现在的图中入度为0和出度为0的点都消灭掉（加边），那么想到这里答案就出来了，就是max{入度为0的点个数，出度为0的点个数}。

#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

#pragma comment(linker, "/STACK:1024000000,1024000000")

#define     IT              iterator
#define     PB(x)           push_back(x)
#define     CLR(a,b)        memset(a,b,sizeof(a))

using namespace std;

typedef     long long               ll;
typedef     unsigned long long      ull;
typedef     vector<int>             vint;
typedef     vector<ll>              vll;
typedef     vector<ull>             vull;
typedef     set<int>                sint;
typedef     set<ull>                sull;

const int maxn = 10000 + 5;
vint G[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int> S;
int a[maxn];

void init(int n) {
    for (int i = 0; i <= n; i++) G[i].clear();
}

void dfs(int u) {
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!pre[v]) {
            dfs(v);
            lowlink[u] = min(lowlink[u],lowlink[v]);
        }
        else if (!sccno[v]) {
            lowlink[u] = min(lowlink[u],pre[v]);
        }
    }
    if (lowlink[u] == pre[u]) {
        scc_cnt++;
        while (1) {
            int x = S.top();
            S.pop();
            sccno[x] = scc_cnt;
            if (x == u) break;
        }
    }
}

void find_scc(int n) {
    dfs_clock = scc_cnt = 0;
    CLR(sccno,0);
    CLR(pre,0);
    for (int i = 1; i <= n; i++) {
        if (!pre[i]) dfs(i);
    }
}

int in[maxn];
int out[maxn];

int main() {
    int n,m;
    //freopen("data.in","r",stdin);
    while (cin>>n) {
        init(n);
        for (int i = 1; i <= n; i++) {
            int m;
            while (scanf("%d",&m),m) {
                G[i].PB(m);
            }
        }
        //for (int i = 0; i <= scc_cnt; i++) new_g[i].clear();
        find_scc(n);
        CLR(in,0);
        CLR(out,0);
        int tmpa = 0,tmpb = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < G[i].size(); j++) {
                int v = G[i][j];
                if (sccno[i] != sccno[v]) {
                    out[sccno[i]]++;
                    in[sccno[v]]++;
                }
            }
        }
        for (int i = 1; i <= scc_cnt; i++) {
            if (!out[i]) tmpb++;
            if (!in[i]) tmpa++;
        }
        cout<<tmpa<<endl<<(scc_cnt == 1 ? 0 : max(tmpb,tmpa))<<endl;
    }
}

 3. POJ 2186 Popular Cows

题目给出一些仰慕关系，需要求的是被所有牛仰慕的牛的个数。由于图相对比较大，所以先强连通缩点，重新构图之后，这样之后就相对简单了，保证图连通的情况下，我们需要保证出度为0的分量只有一个，如果有多个，那么这几个分量之间必然没有倾慕关系。

#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

#pragma comment(linker, "/STACK:1024000000,1024000000")

#define     IT              iterator
#define     PB(x)           push_back(x)
#define     CLR(a,b)        memset(a,b,sizeof(a))

using namespace std;

typedef     long long               ll;
typedef     unsigned long long      ull;
typedef     vector<int>             vint;
typedef     vector<ll>              vll;
typedef     vector<ull>             vull;
typedef     set<int>                sint;
typedef     set<ull>                sull;

const int maxn = 10000 + 5;
vint G[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int> S;
int a[maxn];

void init(int n) {
    for (int i = 0; i <= n; i++) G[i].clear();
}

void dfs(int u) {
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!pre[v]) {
            dfs(v);
            lowlink[u] = min(lowlink[u],lowlink[v]);
        }
        else if (!sccno[v]) {
            lowlink[u] = min(lowlink[u],pre[v]);
        }
    }
    if (lowlink[u] == pre[u]) {
        scc_cnt++;
        while (1) {
            int x = S.top();
            S.pop();
            sccno[x] = scc_cnt;
            if (x == u) break;
        }
    }
}

void find_scc(int n) {
    dfs_clock = scc_cnt = 0;
    CLR(sccno,0);
    CLR(pre,0);
    for (int i = 1; i <= n; i++) {
        if (!pre[i]) dfs(i);
    }
}

int out[maxn];
int cnt[maxn];

int main() {
    int n,m;
    //freopen("data.in","r",stdin);
    while (cin>>n>>m) {
        init(n);
        for (int i = 0; i < m; i++) {
            int a,b;
            scanf("%d%d",&a,&b);
            G[a].PB(b);
        }
        //for (int i = 0; i <= scc_cnt; i++) new_g[i].clear();
        find_scc(n);
        CLR(out,0);
        CLR(cnt,0);
        for (int i = 1; i <= n; i++) {
            cnt[sccno[i]]++;
            for (int j = 0; j < G[i].size(); j++) {
                int v = G[i][j];
                if (sccno[i] != sccno[v]) {
                    out[sccno[i]]++;
                }
            }
        }
        bool flag = true;
        int k = 0;
        for (int i = 1; i <= scc_cnt; i++) {
            if (k && !out[i]) {
                flag = false;
                break;
            }
            if (!out[i]) k = i;
        }
        if (flag) cout<<cnt[k]<<endl;
        else cout<<0<<endl;
    }
}

 4. HDU 3861 The King’s Problem

题目读完之后发现应该是最小路径覆盖，但是两个问题：数据范围和图有环。先强连通缩点，重新构图，这样图就变成了DAG，在应用Hungary算法就可以求出答案了。

#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

#pragma comment(linker, "/STACK:1024000000,1024000000")

#define     IT              iterator
#define     PB(x)           push_back(x)
#define     CLR(a,b)        memset(a,b,sizeof(a))

using namespace std;

typedef     long long               ll;
typedef     unsigned long long      ull;
typedef     vector<int>             vint;
typedef     vector<ll>              vll;
typedef     vector<ull>             vull;
typedef     set<int>                sint;
typedef     set<ull>                sull;

const int maxn = 50000 + 5;
vint G[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int> S;
int a[maxn];

void init(int n) {
    for (int i = 0; i <= n; i++) G[i].clear();
}

void dfs(int u) {
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!pre[v]) {
            dfs(v);
            lowlink[u] = min(lowlink[u],lowlink[v]);
        }
        else if (!sccno[v]) {
            lowlink[u] = min(lowlink[u],pre[v]);
        }
    }
    if (lowlink[u] == pre[u]) {
        scc_cnt++;
        while (1) {
            int x = S.top();
            S.pop();
            sccno[x] = scc_cnt;
            if (x == u) break;
        }
    }
}

void find_scc(int n) {
    dfs_clock = scc_cnt = 0;
    CLR(sccno,0);
    CLR(pre,0);
    for (int i = 1; i <= n; i++) {
        if (!pre[i]) dfs(i);
    }
}

vint new_g[maxn];
int match[maxn];
bool vis[maxn];

bool findpath(int u) {
    for (int i = 0; i < new_g[u].size(); i++) {
        int v = new_g[u][i];
        if (!vis[v]) {
            vis[v] = 1;
            if (match[v] == -1 || findpath(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int hungary() {
    int ans = 0;
    CLR(match,-1);
    for (int i = 1; i <= scc_cnt; i++) {
        CLR(vis,0);
        if (findpath(i)) ans++;
    }
    return ans;
}

int main() {
    //freopen("data.in","r",stdin);
    int n,m;
    int T;
    cin>>T;
    while (T--) {
        cin>>n>>m;
        init(n);
        for (int i = 0; i < m; i++) {
            int a,b;
            scanf("%d%d",&a,&b);
            G[a].PB(b);
        }
        //for (int i = 0; i <= scc_cnt; i++) new_g[i].clear();
        find_scc(n);
        for (int i = 0; i <= scc_cnt; i++) new_g[i].clear();
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < G[i].size(); j++) {
                int v = G[i][j];
                if (sccno[i] != sccno[v]) {
                    new_g[sccno[i]].PB(sccno[v]);
                }
            }
        }
        cout<<scc_cnt - hungary()<<endl;
    }
}

 5. HDU 3639 Hawk-and-Chicken

开始还是老套路，先强连通缩点，需要注意的话这个题重新构图需要反向建边，然后对每个入度0的点DFS，求最大值即可。

#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

#pragma comment(linker, "/STACK:1024000000,1024000000")

#define     IT              iterator
#define     PB(x)           push_back(x)
#define     CLR(a,b)        memset(a,b,sizeof(a))

using namespace std;

typedef     long long               ll;
typedef     unsigned long long      ull;
typedef     vector<int>             vint;
typedef     vector<ll>              vll;
typedef     vector<ull>             vull;
typedef     set<int>                sint;
typedef     set<ull>                sull;

const int maxn = 5000 + 5;
vint G[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int> S;
int a[maxn];

void init(int n) {
    for (int i = 0; i <= n; i++) G[i].clear();
}

void dfs(int u) {
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!pre[v]) {
            dfs(v);
            lowlink[u] = min(lowlink[u],lowlink[v]);
        }
        else if (!sccno[v]) {
            lowlink[u] = min(lowlink[u],pre[v]);
        }
    }
    if (lowlink[u] == pre[u]) {
        scc_cnt++;
        while (1) {
            int x = S.top();
            S.pop();
            sccno[x] = scc_cnt;
            if (x == u) break;
        }
    }
}

void find_scc(int n) {
    dfs_clock = scc_cnt = 0;
    CLR(sccno,0);
    CLR(pre,0);
    for (int i = 0; i < n; i++) {
        if (!pre[i]) dfs(i);
    }
}

vint new_g[maxn];
int rec[maxn];
int out[maxn];
int lab[maxn];
bool vis[maxn];
int cnt;

int dp(int u) {
    vis[u] = true;
    cnt += lab[u];
    for (int i = 0; i < new_g[u].size(); i++) {
        int v = new_g[u][i];
        if (!vis[v]) {
            dp(v);
        }
    }
    return cnt;
}

int main() {
    //freopen("data.in","r",stdin);
    int n,m;
    int T;
    cin>>T;
    for (int t = 1; t <= T; t++) {
        cin>>n>>m;
        init(n);
        for (int i = 0; i < m; i++) {
            int a,b;
            scanf("%d%d",&a,&b);
            G[a].PB(b);
        }
        find_scc(n);
        CLR(out,0);
        CLR(lab,0);
        for (int i = 0; i <= scc_cnt; i++) new_g[i].clear();
        for (int i = 0; i < n; i++) {
            lab[sccno[i]]++;
            for (int j = 0; j < G[i].size(); j++) {
                int v = G[i][j];
                if (sccno[i] != sccno[v]) {
                    new_g[sccno[v]].PB(sccno[i]);
                    out[sccno[i]]++;
                }
            }
        }
        CLR(rec,0);
        int ans = 0;
        for (int i = 1; i <= scc_cnt; i++) {
            if (!out[i]) {
                CLR(vis,0);
                cnt = 0;
                rec[i] = dp(i);
                ans = max(ans,rec[i]);
            }
        }
        /*for (int i = 0; i < n; i++) {
            cout<<sccno[i]<<" ";
        }
        cout<<endl;
        for (int i = 1; i <= scc_cnt; i++) {
            cout<<rec[i][0]<<" "<<rec[i][1]<<endl;
        }*/
        printf("Case %d: %d\n",t,ans - 1);
        bool flag = false;
        for (int i = 0; i < n; i++) {
            if (rec[sccno[i]] == ans) {
                if (flag) printf(" %d",i);
                else {
                    printf("%d",i);
                    flag = true;
                }
            }
        }
        printf("\n");
    }
}

 

连通图练习总结

原文：http://www.cnblogs.com/andybear/p/4395630.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！