首页 > 代码库 > Codeforces Round #286 div.2 D 505D. Mr. Kitayuta's Technology【强连通分量，弱联通分量】

Codeforces Round #286 div.2 D 505D. Mr. Kitayuta's Technology【强连通分量，弱联通分量】

2024-11-20 10:22:01   203人阅读

题目链接：http://codeforces.com/contest/505/problem/D

题目大意：

在一个图中，有n个顶点，给出m对数字（u,v）表示顶点u和顶点v必须直接或者间接相连，让你构造一个这样的图，输出最少需要多少条边。

分析：

毫无疑问，n个顶点的话，我们最多可以用n条边，使得n个顶点构成一个环，满足所有的情况（任意两点都是联通的），但是这并不一定是最少的边。
于是我们还需要找一个方法确定最少需要多少条边。
首先我们利用题目给出的点对建图，得到图G。对于G中的弱联通分量来说，分两种情况讨论：
1.这个弱联通分量中没有环。那么我们能够利用拓扑排序将这个图变成一条链子，假设这个分量中有n1个顶点，那么毫无疑问，所需要的边数为n1-1。
2.这个弱联通分量中有环。假设这个分量中有n2个顶点，那么我们可以用n2条边，将这个n2个顶点构成一个环，
有了上述分析，那么我们现在的工作就是需要判断每个弱联通分量里面有没有环即可。判断环的方法呢，那就是检测这个点所在的强连通分量里点的个数是否等于1，如果大于1，那么说明这个分量中有环，如果等于1,那么说明这个分量中没有环。

代码：
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define N 100010
vector<int> g[N];
vector<int> rg[N];
vector<int> vs;
bool used[N];
int cmp[N];
int n,m;
void add_edge(int from,int to)
{
    g[from].push_back(to);
    rg[to].push_back(from);
}
void dfs(int v)
{
    used[v]=1;
    for(int i=0;i<g[v].size();i++)
        if(!used[g[v][i]])
            dfs(g[v][i]);
    vs.push_back(v);
}
void rdfs(int v,int k)
{
    used[v]=1;
    cmp[v]=k;
    for(int i=0;i<rg[v].size();i++)
        if(!used[rg[v][i]])
            rdfs(rg[v][i],k);
}
int scc()
{
    memset(used,0,sizeof(used));
    vs.clear();
    for(int v=0;v<n;v++)
        if(!used[v])
            dfs(v);
    memset(used,0,sizeof(used));
    int k=0;
    for(int i=vs.size()-1;i>=0;i--)
        if(!used[vs[i]])
            rdfs(vs[i],k++);
    return k;
}
int cmpsize[N];
bool dfs2(int v)
{
    used[v]=1;
    bool ans=(cmpsize[cmp[v]]==1);
    for(int i=0;i<g[v].size();i++)
    {
        if(!used[g[v][i]]) ans &= (dfs2(g[v][i])==1);
    }
    for(int i=0;i<rg[v].size();i++)
    {
        if(!used[rg[v][i]]) ans &= (dfs2(rg[v][i])==1);
    }
    return ans;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(cmpsize,0,sizeof(cmpsize));
        for(int i=0;i<n;i++)
            rg[i].clear(),g[i].clear();

        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add_edge(u-1,v-1);
        }
        scc();
        memset(used,0,sizeof(used));
        for(int i=0;i<n;i++)
            cmpsize[cmp[i]]++;
        int ans=n;
        for(int i=0;i<n;i++)
        {
            if(!used[i])
                ans -= dfs2(i);
        }
        cout<<ans<<endl;
    }
    return 0;
}


Codeforces Round #286 div.2 D 505D. Mr. Kitayuta's Technology【强连通分量，弱联通分量】


联系
我们