首页 > 其他 > 详细

[kuangbin带你飞]专题九 连通图

时间：2015-09-12 12:11:08      阅读：243      评论：0      收藏：0      [点我收藏+]

A. POJ 1236  Network of Schoolst

题意：有n个学校，每个学校都可以给它名单上的学校发送软件。然后现在问你至少需要给多少个学校发送软件。

思路：求出强连通分量的个数，每一个强连通分量需要一个软件。

技术分享 
#include<time.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
//#include<stack>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<math.h>
#include<cctype>
#define ll long long
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define REPP(i,a,b,t) for(int (i)=(a);(i)<=(b);(i)+=(t))
#define rep(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define repp(i,a,b,t) for(int (i)=(a);(i)>=(b);(i)-=(t))
#define PII pair<int,int>
#define fst first
#define snd second
#define MP make_pair
#define PB push_back
#define RI(x) scanf("%d",&(x))
#define RII(x,y) scanf("%d%d",&(x),&(y))
#define RIII(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define DRI(x) int (x);scanf("%d",&(x))
#define DRII(x,y) int (x),(y);scanf("%d%d",&(x),&(y))
#define DRIII(x,y,z) int (x),(y),(z);scanf("%d%d%d",&(x),&(y),&(z))
#define RS(x) scanf("%s",x)
#define RSS(x,y) scanf("%s%s",x,y)
#define DRS(x) char x[maxn];scanf("%s",x)
#define DRSS(x,y) char x[maxn],y[maxn];scanf("%s%s",x,y)
#define MS0(a) memset((a),0,sizeof((a)))
#define MS1(a) memset((a),-1,sizeof((a)))
#define MS(a,b) memset((a),(b),sizeof((a)))
#define ALL(v) v.begin(),v.end()
#define SZ(v) (int)(v).size()


using namespace std;

const int MAXN=200;
int n,cnt,u,v,head,index,t1,t2;
bool edge[MAXN][MAXN];
bool instack[MAXN];
int stack[MAXN];
int low[MAXN];
int dfn[MAXN];
int belong[MAXN];
int in[MAXN];
int out[MAXN];

void init()
{
    head=0;
    index=cnt=1;
    memset(edge,0,sizeof(edge));
    memset(instack,0,sizeof(instack));
    memset(stack,0,sizeof(stack));
    memset(low,0,sizeof(low));
    memset(dfn,-1,sizeof(dfn));
    memset(belong,0,sizeof(belong));
    memset(in,0,sizeof(in));
    memset(out,0,sizeof(out));
    for(int i=0;i<=n;i++)
        dfn[i]=-1;

}

void targan(int u)
{
    low[u]=dfn[u]=index++;
    stack[++head]=u;
    instack[u]=true;
    for(int v=1;v<=n;v++)
    {
        if(!edge[u][v])
            continue;
        if(dfn[v]==-1)
        {
            targan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])
    {
        int temp;
        while(1)
        {
            temp=stack[head--];
            belong[temp]=cnt;
            instack[temp]=false;
            if(temp==u)
                break;
        }
        cnt++;
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d",&n)!=EOF)
    {
        init();
        for(int i=1;i<=n;i++)
        {
            while(scanf("%d",&v)&&v)
                edge[i][v]=true;
        }
        for(int i=1;i<=n;i++)
            if(dfn[i]==-1)
                targan(i);

        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(belong[i]!=belong[j]&&edge[i][j])
                    in[belong[j]]++,out[belong[i]]++;
        for(int i=1;i<cnt;i++)
        {
            if(!in[i])
                t1++;
            if(!out[i])
                t2++;
        }
        if(cnt==2)
            printf("1\n0\n");
        else
            printf("%d\n%d\n",t1,max(t1,t2));
    }
    return 0;
}
View Code

B. UVA 315  Network

题意：有n个点，其中一些点删除后那么可能某些点之间就不能通信了，问你这样的点有多少个。

思路：求割点的裸题。

技术分享 
#include<time.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<math.h>
#include<cctype>
#define ll long long
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define REPP(i,a,b,t) for(int (i)=(a);(i)<=(b);(i)+=(t))
#define rep(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define repp(i,a,b,t) for(int (i)=(a);(i)>=(b);(i)-=(t))
#define PII pair<int,int>
#define fst first
#define snd second
#define MP make_pair
#define PB push_back
#define RI(x) scanf("%d",&(x))
#define RII(x,y) scanf("%d%d",&(x),&(y))
#define RIII(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define DRI(x) int (x);scanf("%d",&(x))
#define DRII(x,y) int (x),(y);scanf("%d%d",&(x),&(y))
#define DRIII(x,y,z) int (x),(y),(z);scanf("%d%d%d",&(x),&(y),&(z))
#define RS(x) scanf("%s",x)
#define RSS(x,y) scanf("%s%s",x,y)
#define DRS(x) char x[maxn];scanf("%s",x)
#define DRSS(x,y) char x[maxn],y[maxn];scanf("%s%s",x,y)
#define MS0(a) memset((a),0,sizeof((a)))
#define MS1(a) memset((a),-1,sizeof((a)))
#define MS(a,b) memset((a),(b),sizeof((a)))
#define ALL(v) v.begin(),v.end()
#define SZ(v) (int)(v).size()


using namespace std;

const int MAXN=10010;
const int MAXM=100010;

int n,u,v,cnt,inde;
char ch;
int dfn[MAXN];
int low[MAXN];
vector<int> G[MAXN];
bool cut[MAXN];
bool g[110][110];
void Targan(int u,int pre)
{
    low[u]=dfn[u]=++inde;
    int son=0;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==pre)
            continue;
        if(dfn[v]==-1)
        {
            son++;
            Targan(v,u);
            low[u]=min(low[u],low[v]);
            if(u!=pre&&low[v]>=dfn[u])
                cut[u]=true;
        }
        else
            low[u]=min(low[u],dfn[v]);
    }
    if(u==pre&&son>1) cut[u]=true;
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d",&n)&&n)
    {
        memset(cut,0,sizeof(cut));
        memset(g,0,sizeof(g));
        for(int i=0;i<=n;i++)
            G[i].clear();
        cnt=inde=0;
        while(scanf("%d",&u)&&u)
        {
            while(1)
            {
                scanf("%d",&v);
                g[u][v]=g[v][u]=true;
                ch=getchar();
                if(ch==‘\n‘)
                    break;
            }

        }
        for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++)
                if(g[i][j]&&i!=j) G[i].push_back(j);
        for(int i=0;i<=n;i++)
            dfn[i]=-1;
        for(int i=1;i<=n;i++)
            if(dfn[i]==-1)
                Targan(i,i);

        for(int i=1;i<=n;i++)
            if(cut[i])  cnt++;
        printf("%d\n",cnt);
    }
    return 0;
}
View Code

C. UVA 796  Critical Links

题意：按字典序输出所有的割边。

技术分享 
#include<time.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<math.h>
#include<cctype>
#define ll long long
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define REPP(i,a,b,t) for(int (i)=(a);(i)<=(b);(i)+=(t))
#define rep(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define repp(i,a,b,t) for(int (i)=(a);(i)>=(b);(i)-=(t))
#define PII pair<int,int>
#define fst first
#define snd second
#define MP make_pair
#define PB push_back
#define RI(x) scanf("%d",&(x))
#define RII(x,y) scanf("%d%d",&(x),&(y))
#define RIII(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define DRI(x) int (x);scanf("%d",&(x))
#define DRII(x,y) int (x),(y);scanf("%d%d",&(x),&(y))
#define DRIII(x,y,z) int (x),(y),(z);scanf("%d%d%d",&(x),&(y),&(z))
#define RS(x) scanf("%s",x)
#define RSS(x,y) scanf("%s%s",x,y)
#define DRS(x) char x[maxn];scanf("%s",x)
#define DRSS(x,y) char x[maxn],y[maxn];scanf("%s%s",x,y)
#define MS0(a) memset((a),0,sizeof((a)))
#define MS1(a) memset((a),-1,sizeof((a)))
#define MS(a,b) memset((a),(b),sizeof((a)))
#define ALL(v) v.begin(),v.end()
#define SZ(v) (int)(v).size()


using namespace std;

const int MAXN=10010;
const int MAXM=100010;

struct Edge{
    int u,v,id;
}e[MAXM];
int n,m,u,v,cnt,inde,id;
char ch;
int dfn[MAXN];
int low[MAXN];
bool g[MAXN][MAXN];
vector<Edge> G[MAXN];
bool cut[MAXM];

void init()
{
    memset(e,0,sizeof(e));
    memset(g,0,sizeof(g));
    memset(cut,0,sizeof(cut));
    for(int i=0;i<n;i++)
        G[i].clear();
    cnt=inde=id=0;
}

void Targan(int u,int pre)
{
    low[u]=dfn[u]=++inde;
    for(int i=0;i<G[u].size();i++)
    {
        Edge e=G[u][i];
        if(e.v==pre)
            continue;
        if(dfn[e.v]==-1)
        {
            Targan(e.v,u);
            low[u]=min(low[u],low[e.v]);
            if(low[e.v]>dfn[u])
            {
                cut[e.id]=true;
                cnt++;
            }
        }
        else
            low[u]=min(low[u],dfn[e.v]);
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d",&n)!=EOF)
    {
        init();
        for(int i=0;i<n;i++)
        {
            scanf("%d (%d)",&u,&m);
            for(int j=0;j<m;j++)
            {
                scanf("%d",&v);
                g[u][v]=true;
            }
        }

        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
            {
                if(g[i][j])
                {
                    G[i].push_back({i,j,id});
                    G[j].push_back({j,i,id});
                    e[id]={i,j,id};
                    id++;
                }
            }

        for(int i=0;i<n;i++)
            dfn[i]=-1;
        for(int i=0;i<n;i++)
            if(dfn[i]==-1)
                Targan(i,i);
        printf("%d critical links\n",cnt);
        for(int i=0;i<id;i++)
            if(cut[i])
                printf("%d - %d\n",e[i].u,e[i].v);
        puts("");
    }
    return 0;
}
View Code

D. POJ 3694  Network

题意：有一个图，有Q次加边，要求你输出每次加边后的桥/割边的个数。

思路：对于每次输入，求他们的最近公共祖先，而求最近公共祖先的过程中遇到的割点去掉。然后再删去一条割边。

技术分享 
#include<time.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<math.h>
#include<cctype>
#define ll long long
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define REPP(i,a,b,t) for(int (i)=(a);(i)<=(b);(i)+=(t))
#define rep(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define repp(i,a,b,t) for(int (i)=(a);(i)>=(b);(i)-=(t))
#define PII pair<int,int>
#define fst first
#define snd second
#define MP make_pair
#define PB push_back
#define RI(x) scanf("%d",&(x))
#define RII(x,y) scanf("%d%d",&(x),&(y))
#define RIII(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define DRI(x) int (x);scanf("%d",&(x))
#define DRII(x,y) int (x),(y);scanf("%d%d",&(x),&(y))
#define DRIII(x,y,z) int (x),(y),(z);scanf("%d%d%d",&(x),&(y),&(z))
#define RS(x) scanf("%s",x)
#define RSS(x,y) scanf("%s%s",x,y)
#define DRS(x) char x[maxn];scanf("%s",x)
#define DRSS(x,y) char x[maxn],y[maxn];scanf("%s%s",x,y)
#define MS0(a) memset((a),0,sizeof((a)))
#define MS1(a) memset((a),-1,sizeof((a)))
#define MS(a,b) memset((a),(b),sizeof((a)))
#define ALL(v) v.begin(),v.end()
#define SZ(v) (int)(v).size()


using namespace std;

const int MAXN=110000;
const int MAXM=220000;

struct Edge{
    int u,v,id;
}e[MAXM];
int n,m,u,v,cnt,inde,q;
char ch;
int DFN[MAXN];
int dfn[MAXN];
int low[MAXN];
int pre[MAXN];
//bool g[MAXN][MAXN];
vector<int> G[MAXN];
bool cut[MAXN];

void init()
{
    memset(e,0,sizeof(e));
    //memset(g,0,sizeof(g));
    memset(cut,0,sizeof(cut));
    memset(pre,0,sizeof(pre));
    memset(DFN,0,sizeof(DFN));
    for(int i=0;i<n;i++)
        G[i].clear();
    cnt=inde=0;
}

void Targan(int u)
{
    low[u]=dfn[u]=++inde;
    DFN[u]=DFN[pre[u]]+1;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(dfn[v]==-1)
        {
            pre[v]=u;
            Targan(v);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])
            {
                cnt++;
                cut[v]=true;
            }
        }
        else if(v!=pre[u])
            low[u]=min(low[u],dfn[v]);
    }
}

void lca(int u,int v)
{
    if(DFN[u]<DFN[v])
        swap(u,v);
    while(DFN[u]>DFN[v])
    {
        if(cut[u])
            cnt--,cut[u]=false;
        u=pre[u];
    }
    while(u!=v)
    {
        if(cut[u])
            cnt--,cut[u]=false;
        if(cut[v])
            cnt--,cut[v]=false;
        u=pre[u];
        v=pre[v];
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    int icase=0;
    while(scanf("%d%d",&n,&m)&&n&&m)
    {
        ++icase;
        init();
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        for(int i=0;i<=n;i++)
            dfn[i]=-1;
        for(int i=1;i<=n;i++)
            if(dfn[i]==-1)
                Targan(i);
        printf("Case %d:\n",icase);
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d%d",&u,&v);
            lca(u,v);
            printf("%d\n",cnt);
        }
        puts("");
    }
    return 0;
}
View Code

 E. POJ 3177  Redundant Paths

题意：给你一个图，问你至少需要加多少条边可以使得图没有桥/割边。

思路：缩联通分量成点，然后统计度数为2的点，输出(点数+1)/2.

技术分享 
#include<time.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
//#include<stack>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<math.h>
#include<cctype>
#define ll long long
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define REPP(i,a,b,t) for(int (i)=(a);(i)<=(b);(i)+=(t))
#define rep(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define repp(i,a,b,t) for(int (i)=(a);(i)>=(b);(i)-=(t))
#define PII pair<int,int>
#define fst first
#define snd second
#define MP make_pair
#define PB push_back
#define RI(x) scanf("%d",&(x))
#define RII(x,y) scanf("%d%d",&(x),&(y))
#define RIII(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define DRI(x) int (x);scanf("%d",&(x))
#define DRII(x,y) int (x),(y);scanf("%d%d",&(x),&(y))
#define DRIII(x,y,z) int (x),(y),(z);scanf("%d%d%d",&(x),&(y),&(z))
#define RS(x) scanf("%s",x)
#define RSS(x,y) scanf("%s%s",x,y)
#define DRS(x) char x[maxn];scanf("%s",x)
#define DRSS(x,y) char x[maxn],y[maxn];scanf("%s%s",x,y)
#define MS0(a) memset((a),0,sizeof((a)))
#define MS1(a) memset((a),-1,sizeof((a)))
#define MS(a,b) memset((a),(b),sizeof((a)))
#define ALL(v) v.begin(),v.end()
#define SZ(v) (int)(v).size()


using namespace std;

const int MAXN=6000;
const int MAXM=25000;

struct Edge{
    int u,v,id;
    bool cut;
}e[MAXM];
int n,m,u,v,cnt,inde,top,block;
char ch;
int dfn[MAXN];
int low[MAXN];
int pre[MAXN];
//bool g[MAXN][MAXN];
vector<Edge> G[MAXN];
bool cut[MAXN];
bool instack[MAXN];
int stack[MAXN];
int belong[MAXN];
int in[MAXN];
void init()
{
    memset(e,0,sizeof(e));
    //memset(g,0,sizeof(g));
    memset(cut,0,sizeof(cut));
    memset(pre,0,sizeof(pre));
    memset(stack,0,sizeof(stack));
    memset(belong,0,sizeof(belong));
    memset(in,0,sizeof(in));
    memset(instack,0,sizeof(instack));
    //memset(DFN,0,sizeof(DFN));
    for(int i=0;i<=n;i++)
        G[i].clear();
    cnt=inde=0;
}

void Targan(int u)
{
    low[u]=dfn[u]=++inde;
    stack[top++]=u;
    instack[u]=true;
    for(int i=0;i<G[u].size();i++)
    {
        Edge en=G[u][i];
        if(en.v==pre[u]) continue;
        if(dfn[en.v]==-1)
        {
            pre[en.v]=u;
            Targan(en.v);
            low[u]=min(low[u],low[en.v]);
            if(low[en.v]>dfn[u])
            {
                e[en.id].cut=true;
                e[en.id^1].cut=true;
            }
        }
        else if(instack[en.v])
            low[u]=min(low[u],dfn[en.v]);
    }
    if(low[u]==dfn[u])
    {
        block++;
        int temp;
        do{
            temp=stack[--top];
            instack[temp]=false;
            belong[temp]=block;
        }while(temp!=u);
    }
}
/*
void lca(int u,int v)
{
    if(DFN[u]<DFN[v])
        swap(u,v);
    while(DFN[u]>DFN[v])
    {
        if(cut[u])
            cnt--,cut[u]=false;
        u=pre[u];
    }
    while(u!=v)
    {
        if(cut[u])
            cnt--,cut[u]=false;
        if(cut[v])
            cnt--,cut[v]=false;
        u=pre[u];
        v=pre[v];
    }
}
*/
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            G[u].push_back({u,v,i*2,false});
            G[v].push_back({v,u,i*2+1,false});
            e[2*i]={u,v,i*2,false};
            e[2*i+1]={v,u,i*2+1,false};
        }
        for(int i=0;i<=n;i++)
            dfn[i]=-1;
        for(int i=1;i<=n;i++)
            if(dfn[i]==-1)
                Targan(i);


        for(int u=1;u<=n;u++)
            for(int i=0;i<G[u].size();i++)
                if(e[G[u][i].id].cut)
                    in[belong[u]]++;
        for(int i=1;i<=block;i++)
            if(in[i]==1)
                cnt++;
        printf("%d\n",(cnt+1)/2);
    }
    return 0;
}
View Code

F. HDU 4612  Warm up

题意：给你一个图，注意可能有重边，你可以在图中加一条边，问你加入一条边后最少的桥边树。

思路：先缩联通分量成点，然后统计出桥边的条数，再两遍bfs，找出直径，然后减去直径上桥边的数量，即为所求。

技术分享 
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int,int> P;
const int MAXN=200005;
const int MAXM=2000005;
struct Edge{
    int u,v,id;
};
vector <Edge> G[MAXN];
vector <int> G2[MAXN];
queue<P> q;
int n,m,u,v,index,tag,top,deep,cnt,block;
int dfn[MAXN];
int low[MAXN];
int cut[MAXN];
int vis[MAXN];

int stack[MAXN];
int belong[MAXN];

void init()
{
    memset(dfn,0,sizeof(dfn));
    memset(cut,0,sizeof(cut));
    memset(low,0,sizeof(low));
    memset(belong,0,sizeof(belong));
    for(int i=0;i<MAXN;i++)
        G[i].clear(),G2[i].clear();
    cnt=index=top=block=0;
}
void Targan(int u,int la)
{
    low[u]=dfn[u]=++index;
    stack[++top]=u;
    for(int i=0;i<G[u].size();i++)
    {
        Edge e=G[u][i];
        if(e.id==la)
            continue;
        if(!dfn[e.v])
        {
            Targan(e.v,e.id);
            low[u]=min(low[u],low[e.v]);
            if(low[e.v]>dfn[u])
            {
                cnt++;
                cut[e.v]=true;
            }
        }
        else
            low[u]=min(low[u],dfn[e.v]);
    }
    if(low[u]==dfn[u])
    {
        block++;
        do{
            v=stack[top--];
            belong[v]=block;
        }while(u!=v);
    }
}

void bfs(int flag)
{
    deep=0;
    while(!q.empty())
        q.pop();
    memset(vis,0,sizeof(vis));
    q.push({flag,0});
    vis[flag]=true;
    while(!q.empty())
    {
        P p=q.front();
        if(p.second>=deep)
        {
            deep=p.second;
            tag=p.first;
        }
        q.pop();
        for(int i=0;i<G2[p.first].size();i++)
        {
            int v=G2[p.first][i];
            if(!vis[v])
            {
                vis[v]=true;
                q.push({v,p.second+1});
            }
        }
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m)&&n&&m)
    {
        init();
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            G[u].push_back({u,v,i});
            G[v].push_back({v,u,i});
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i])
                Targan(i,-1);

        for(int u=1;u<=n;u++)
        {
            for(int v=0;v<G[u].size();v++)
            {
                if(belong[u]!=belong[G[u][v].v])
                {
                    G2[belong[u]].push_back(belong[G[u][v].v]);
                    G2[belong[G[u][v].v]].push_back(belong[u]);
                }
            }
        }

        bfs(1);
        bfs(tag);

        printf("%d\n",cnt-deep);

    }
}
View Code

G. HDU 4635  Strongly connected

题意：给你一个不是强连通的图，你最多加入多少条边，使得这个图依旧不是强连通的。

思路：缩联通分量成点，然后找出只有入度或者只有出度且度数最少的点，设这个点所包含的节点数为cnt，那么我们加边之后的结果应该是n^n-n-m-cnt*(n-cnt)。减n是去掉自环，减m是去掉已有的边，减去cnt*（n-cnt）是因为这个点跟其他的点就不能再连边了，不然就只有一个强连通分量了。

技术分享 
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int,int> P;
const int MAXN=200005;
const int MAXM=2000005;
struct Edge{
    int u,v,id;
};
vector <Edge> G[MAXN];
vector <int> G2[MAXN];
queue<P> q;
int n,m,u,v,index,tag,top,deep,cnt,block;
int dfn[MAXN];
int low[MAXN];
int cut[MAXN];
int vis[MAXN];

int stack[MAXN];
int belong[MAXN];

void init()
{
    memset(dfn,0,sizeof(dfn));
    memset(cut,0,sizeof(cut));
    memset(low,0,sizeof(low));
    memset(belong,0,sizeof(belong));
    for(int i=0;i<MAXN;i++)
        G[i].clear(),G2[i].clear();
    cnt=index=top=block=0;
}
void Targan(int u,int la)
{
    low[u]=dfn[u]=++index;
    stack[++top]=u;
    for(int i=0;i<G[u].size();i++)
    {
        Edge e=G[u][i];
        if(e.id==la)
            continue;
        if(!dfn[e.v])
        {
            Targan(e.v,e.id);
            low[u]=min(low[u],low[e.v]);
            if(low[e.v]>dfn[u])
            {
                cnt++;
                cut[e.v]=true;
            }
        }
        else
            low[u]=min(low[u],dfn[e.v]);
    }
    if(low[u]==dfn[u])
    {
        block++;
        do{
            v=stack[top--];
            belong[v]=block;
        }while(u!=v);
    }
}

void bfs(int flag)
{
    deep=0;
    while(!q.empty())
        q.pop();
    memset(vis,0,sizeof(vis));
    q.push({flag,0});
    vis[flag]=true;
    while(!q.empty())
    {
        P p=q.front();
        if(p.second>=deep)
        {
            deep=p.second;
            tag=p.first;
        }
        q.pop();
        for(int i=0;i<G2[p.first].size();i++)
        {
            int v=G2[p.first][i];
            if(!vis[v])
            {
                vis[v]=true;
                q.push({v,p.second+1});
            }
        }
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m)&&n&&m)
    {
        init();
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            G[u].push_back({u,v,i});
            G[v].push_back({v,u,i});
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i])
                Targan(i,-1);

        for(int u=1;u<=n;u++)
        {
            for(int v=0;v<G[u].size();v++)
            {
                if(belong[u]!=belong[G[u][v].v])
                {
                    G2[belong[u]].push_back(belong[G[u][v].v]);
                    G2[belong[G[u][v].v]].push_back(belong[u]);
                }
            }
        }

        bfs(1);
        bfs(tag);

        printf("%d\n",cnt-deep);

    }
}
View Code

I. HDU 4738  Caocao‘s Bridges

题意：告诉你n个岛，岛与岛之间有m座桥。周瑜希望让诸葛亮去炸掉桥边。而桥上有士兵，诸葛亮带领的士兵必须要大于等于桥上的士兵，问你最少需要派遣多少士兵。

思路：求出权值最小的割边就好。但是要注意如果桥上没人，要输出0而不是1。

技术分享 
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int,int> P;
const int MAXN=200005;
const int MAXM=2000005;
struct Edge{
    int u,v,id;
};
vector <Edge> G[MAXN];
vector <int> G2[MAXN];
queue<P> q;
int n,m,u,v,index,tag,top,deep,cnt,block;
int dfn[MAXN];
int low[MAXN];
int cut[MAXN];
int vis[MAXN];

int stack[MAXN];
int belong[MAXN];

void init()
{
    memset(dfn,0,sizeof(dfn));
    memset(cut,0,sizeof(cut));
    memset(low,0,sizeof(low));
    memset(belong,0,sizeof(belong));
    for(int i=0;i<MAXN;i++)
        G[i].clear(),G2[i].clear();
    cnt=index=top=block=0;
}
void Targan(int u,int la)
{
    low[u]=dfn[u]=++index;
    stack[++top]=u;
    for(int i=0;i<G[u].size();i++)
    {
        Edge e=G[u][i];
        if(e.id==la)
            continue;
        if(!dfn[e.v])
        {
            Targan(e.v,e.id);
            low[u]=min(low[u],low[e.v]);
            if(low[e.v]>dfn[u])
            {
                cnt++;
                cut[e.v]=true;
            }
        }
        else
            low[u]=min(low[u],dfn[e.v]);
    }
    if(low[u]==dfn[u])
    {
        block++;
        do{
            v=stack[top--];
            belong[v]=block;
        }while(u!=v);
    }
}

void bfs(int flag)
{
    deep=0;
    while(!q.empty())
        q.pop();
    memset(vis,0,sizeof(vis));
    q.push({flag,0});
    vis[flag]=true;
    while(!q.empty())
    {
        P p=q.front();
        if(p.second>=deep)
        {
            deep=p.second;
            tag=p.first;
        }
        q.pop();
        for(int i=0;i<G2[p.first].size();i++)
        {
            int v=G2[p.first][i];
            if(!vis[v])
            {
                vis[v]=true;
                q.push({v,p.second+1});
            }
        }
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m)&&n&&m)
    {
        init();
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            G[u].push_back({u,v,i});
            G[v].push_back({v,u,i});
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i])
                Targan(i,-1);

        for(int u=1;u<=n;u++)
        {
            for(int v=0;v<G[u].size();v++)
            {
                if(belong[u]!=belong[G[u][v].v])
                {
                    G2[belong[u]].push_back(belong[G[u][v].v]);
                    G2[belong[G[u][v].v]].push_back(belong[u]);
                }
            }
        }

        bfs(1);
        bfs(tag);

        printf("%d\n",cnt-deep);

    }
}
View Code

 

[kuangbin带你飞]专题九 连通图

原文：http://www.cnblogs.com/onlyAzha/p/4802320.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 版权所有
打开技术之扣，分享程序人生！