首页 > 代码库 > UVALive 4287 SCC-Tarjan 加边变成强连通分量

UVALive 4287 SCC-Tarjan 加边变成强连通分量

2024-07-16 19:00:12   226人阅读

还是强连通分量的题目，但是这个题目不同的在于，问你最少要添加多少条有向边，使得整个图变成一个强连通分量

然后结论是，找到那些入度为0的点的数目 和 出度为0的点的数目，取其最大值即可，怎么证明嘛。。。我也不好怎么证，不过细细一琢磨发现就是这样，改天找聪哥一起探讨下怎么证明

#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <stack>using namespace std;const int N=20010;int pre[N],lowlink[N],sccno[N];vector<int>G[N],G2[N];stack<int> sta;int n,m,vis[N],scc_cnt,dfs_clk;int ind[N],outd[N];void init(){    for (int i=0;i<=n;i++){        pre[i]=0;        lowlink[i]=0;        sccno[i]=0;        G[i].clear();        G2[i].clear();        vis[i]=0;        scc_cnt=dfs_clk=0;        ind[i]=outd[i]=0;    }}void dfs(int u){    pre[u]=lowlink[u]=++dfs_clk;    sta.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++;        for (;;){            int x=sta.top();sta.pop();            sccno[x]=scc_cnt;            if (x==u) break;        }    }}void tarjan(){    for (int i=1;i<=n;i++){        if (!pre[i]) dfs(i);    }    for (int i=1;i<=n;i++){        int u=sccno[i];        for (int j=0;j<G[i].size();j++){            int v=G[i][j];            v=sccno[v];            if (u!=v){                G2[u].push_back(v);                ind[v]++;                outd[u]++;            }        }    }}int main(){    int t;    scanf("%d",&t);    while (t--)    {        scanf("%d%d",&n,&m);        init();        int a,b;        while (m--){            scanf("%d%d",&a,&b);            G[a].push_back(b);        }        tarjan();        if (scc_cnt==1){            puts("0");            continue;        }        int ans1=0,ans2=0;        for (int i=1;i<=scc_cnt;i++){            if (ind[i]==0) ans1++;            if (outd[i]==0) ans2++;        }        printf("%d\n",max(ans1,ans2));    }    return 0;}

　　


联系
我们