首页 > Web开发 > 详细

POJ1236 Network of schools

时间:2020-02-15 20:13:20      阅读:66      评论:0      收藏:0      [点我收藏+]

解决两个问题,对于给定的有向图,需要给多少个点可以遍历整个图,需要加多少条边可以使整个图变得强连通~

思路:用tarjan进行缩点,得到一个scc图,算出有n个入度为0的点,m个出度为0的点,第一个答案就是n,第二个答案就是max(n,m)

#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int maxn=1014;
vector<int> g[maxn];
int N,M,x,y;
int low[maxn];
int dfn[maxn];
int cnt;
int scc;
int pos[maxn];
int in[maxn];
int out[maxn];
stack<int> st;
void tarjan (int x) {
    low[x]=dfn[x]=++cnt;
    st.push(x);
    for (int i=0;i<g[x].size();i++) {
        if (!low[g[x][i]]) {
            tarjan(g[x][i]);
            low[x]=min(low[x],low[g[x][i]]);
        }
        else if (!pos[g[x][i]])low[x]=min(low[x],dfn[g[x][i]]);
    }
    if (low[x]==dfn[x]) {
        scc++;
        while (1) {
            int u=st.top();
            st.pop();
            low[u]=low[x];
            pos[u]=scc;
            if (u==x) break;
        }
    }
} 
void build () {
    for (int i=1;i<=N;i++) {
        for (int j=0;j<g[i].size();j++) {
            if (pos[i]!=pos[g[i][j]]) {
                out[pos[i]]++;
                in[pos[g[i][j]]]++;
            }
        }
    }
}
int main () {
    scanf ("%d",&N);
    for (int i=1;i<=N;i++) {
        while (scanf("%d",&x)&&x) g[i].push_back(x);
    }
    for (int i=1;i<=N;i++) 
    if (!low[i]) tarjan(i);
    build ();
    int rd=0;
    int cd=0;
    for (int i=1;i<=scc;i++) {
        if (in[i]==0) rd++;
        if (out[i]==0) cd++;
    }
    if (scc==1) printf ("1\n0\n");
    else printf ("%d\n%d\n",rd,max(rd,cd));
    return 0;
}

 

POJ1236 Network of schools

原文:https://www.cnblogs.com/zhanglichen/p/12313247.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!