图论复习总结

0.格式

适用范围

算法思想

代码实现：空间申请，初始化，算法步骤，输入输出，时间复杂度

1.dijkstra算法

适用范围：图论相关，单源最短路求法，无负权边，

算法思想：bfs，贪心。不断的使用可达集合中未被使用的最短的端点信息更新到达每一个顶点最短距离信息。

代码实现：

plan A：使用邻接矩阵储存边信息（不可达初始化为无穷)，使用数组维护最短路信息（初始化为无穷），使用数组维护到达每个端点的路径（数组保存元素表示上一个顶点，初始化为-1），使用数组维护未被访问集合（初始化为0表示未被访问）。

输入：V，E，源点。

初始化，让源点直接相连顶点的最短距离更新为最短直接相连距离。设置源点被访问。

每一步遍历找到最短未被访问端点，记它为已访问，用它更新其他顶点的最短路信息。

输出：到每个端点的最短路。

时间复杂度：O(n^2)

代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn=1010;
#define typec int
const typec INF = 0x3f3f3f3f;
bool vis[maxn];
int pre[maxn];
int cost[maxn][maxn];
int lowcost[maxn];
void dijkstra(typec cost[][maxn],typec lowcost[],int n,int beg){
    for(int i=0;i<n;i++){
        lowcost[i]=INF;vis[i]=false;pre[i]=-1;
    }
    lowcost[beg]=0;
    for(int j=0;j<n;j++){
        int k=-1;
        int Min=INF;
        for(int i=0;i<n;i++){
            if(!vis[i]&&lowcost[i]<Min){
                Min=lowcost[i];
                k=i;
            }
        }
        if(k==-1)break;
        vis[k]=true;
        for(int i=0;i<n;i++){
            if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i]){
                lowcost[i]=lowcost[k]+cost[k][i];
                pre[i]=k;
            }
        }
    }
}


int main(){
    int n,m,s;
    cin >> n >> m >> s;
    s--;
    int fi,gi,wi;
    memset(cost,0x3f,sizeof(cost));
    for(int i=0;i<m;i++){
        cin >> fi >> gi >> wi;
        fi--;gi--;
        cost[fi][gi]=min(wi,cost[fi][gi]);
    }
    dijkstra(cost,lowcost,n,s);
    for(int i=0;i<n;i++){
        printf("%d%c",lowcost[i],i==n-1?'
':' ');
    }
}
View Code

plan B 优先队列优化，优先队列维护可达点集信息，包括端点下标和到端点最短距离，以最短距离排队从小到大排列。邻接表维护边信息，使用vector数组，数组下标表示出发点，元素内包含达到点和边权。使用数组维护未被访问集合（初始化为0表示未被访问）。使用数组维护最短路信息（初始化为无穷）

bfs：将源点加入到优先队列内，之后直到优先队列为空，取出队列中最顶端元素，将他记为已访问（若本身已访问则改为跳过），之后用以它为出发点的所有边的信息来更新到达点的最短距离信息并将它们加入到队列中。

输入输出与上一致但是没有路径信息。

时间复杂度：O（ElogE）

代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int INF=0x3f3f3f3f;
 5 const int MAXN=1000010;
 6 struct qnode {
 7     int v;
 8     int c;
 9     qnode(int _v=0,int _c=0):v(_v),c(_c){}
10     bool operator <(const qnode &r)const{
11         return c>r.c;
12     }
13 };
14 
15 struct Edge{
16     int v,cost;
17     Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
18 };
19 vector<Edge> E[MAXN];
20 bool vis[MAXN];
21 int dist[MAXN];
22 
23 void Dijkstra(int n,int start){
24     memset(vis,false,sizeof(vis));
25     for(int i=1;i<=n;i++)dist[i]=INF;
26     priority_queue <qnode>que;
27     while(!que.empty())que.pop();
28     dist[start]=0;
29     que.push(qnode(start,0));
30     qnode tmp;
31     while(!que.empty()){
32         tmp=que.top();
33         que.pop();
34         int u=tmp.v;
35         if(vis[u])continue;
36         vis[u]=true;
37         for(int i=0;i<E[u].size();i++){
38             int v=E[u][i].v;
39             int cost=E[u][i].cost;
40             if(!vis[v]&&dist[v]>dist[u]+cost){
41                 dist[v]=dist[u]+cost;
42                 que.push(qnode(v,dist[v]));
43             }
44         }
45 
46     }
47 }
48 
49 void addedge(int u,int v,int w){
50     E[u].push_back(Edge(v,w));
51 }
52 int main()
53 {
54     int n,m,s;
55     cin >> n >> m >> s;
56     for(int i=0;i<m ;i++){
57         int a,b,c;
58         cin >> a >> b >>c;
59         addedge(a,b,c);
60 
61     }
62     Dijkstra(n,s);
63 
64     for(int i=1;i<=n;i++){
65         printf("%d ",dist[i]);
66     }
67     printf("
");
68 }
View Code

2.bellman_ford算法

适用范围：单源最短路算法，可以适用判断有无负环回路

算法思想：动态规划，用每一条边更新点的最短路信息

代码实现：设置最短路数组、边集数组、初始化最短路信息为无穷，设置起始点最短路为0，对于每一条边用它更新它到达点的最短路信息，由于最短路不可能有环，因此最多更新V-1次即可找到最短路。

时间复杂度O（VE）

代码：

#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=550;
int dist[MAXN];
struct Edge
{
    int u,v;
    int cost;
    Edge(int _u=0,int _v=0,int _cost=0):u(_u),v(_v),cost(_cost){}
};
vector<Edge>E;
bool bellman_ford(int start,int n)
{
    for(int i=1; i<=n; i++)
        dist[i]=INF;
    dist[start]=0;//最多做 n-1 次
    for(int i=1; i<n; i++)
    {
        bool flag=false;
        for(int j=0; j<E.size(); j++)
        {
            int u=E[j].u;
            int v=E[j].v;
            int cost=E[j].cost;
            if(dist[v]>dist[u]+cost)
            {
                dist[v]=dist[u]+cost;
                flag=true;
            }
        }
        if(!flag)
            return true;//没有负环回路
    }
    for(int j=0; j<E.size(); j++)
        if(dist[E[j].v]>dist[E[j].u]+E[j].cost)
            return false;//有负环回路
    return true;//没有负环回
}
View Code

3.单源最短路SPFA

适用范围：单源最短路算法，可以适用判断有无负环回路

算法思想：设置一个集合，每次用集合中点的相关边来更新相邻点信息，让相邻点入集合，当前点出集合

代码实现：设置邻接表，设置在队列标志数组，每个点入队次数数组，距离数组，让源点入队列，让源点访问次数为1，之后直到队列空，每次取出队首元素，让它记为未被访问。之后对于以该点为出发点的边，更新队列和最短路信息。

时间复杂度不定，O（kE）。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1010;
const int INF=0x3f3f3f3f;
struct Edge
{
    int v;
    int cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost) {}
};
vector<Edge>E[MAXN];
void addedge(int u,int v,int w)
{
    E[u].push_back(Edge(v,w));
}
bool vis[MAXN];//在队列标志
int cnt[MAXN];
//每个点的入队列次数
int dist[MAXN];
bool SPFA(int start,int n)
{
    memset(vis,false,sizeof(vis));
    for(int i=1; i<=n; i++)
        dist[i]=INF;
    vis[start]=true;
    dist[start]=0;
    queue<int>que;
    while(!que.empty())
        que.pop();
    que.push(start);
    memset(cnt,0,sizeof(cnt));
    cnt[start]=1;
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;
        for(int i=0; i<E[u].size(); i++)
        {
            int v=E[u][i].v;
            if(dist[v]>dist[u]+E[u][i].cost)
            {
                dist[v]=dist[u]+E[u][i].cost;
                if(!vis[v])
                {
                    vis[v]=true;
                    que.push(v);
                    if(++cnt[v]>n)
                        return false;//cnt[i] 为入队列次数，用来判定是否存在负环回路
                }
            }
        }
    }
    return true;
}
View Code

4.prim算法 

适用范围：最小生成树MST

算法思想：每次找到当前集合到其他点的最短边，加入这条边并用这条边的信息更新当前集合到其他点的最短路信息。

代码实现：设置当前集合到其他点的最短路信息集合数组，访问数组，首先将最短路信息设置为任意一点到其他点的距离，之后用最短的一个更新信息。

时间复杂度：O（n^2)

#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=110;
bool vis[MAXN];
int lowc[MAXN];//点是 0 n-1
int Prim(int cost[][MAXN],int n)
{
    int ans=0;
    memset(vis,false,sizeof(vis));
    vis[0]=true;
    for(int i=1; i<n; i++)
        lowc[i]=cost[0][i];
    for(int i=1; i<n; i++)
    {
        int minc=INF;
        int p=-1;
        for(int j=0; j<n; j++)
            if(!vis[j]&&minc>lowc[j])
            {
                minc=lowc[j];
                p=j;
            }
        if(minc==INF)
            return -1;//原图不连通
        ans+=minc;
        vis[p]=true;
        for(int j=0; j<n; j++)
            if(!vis[j]&&lowc[j]>cost[p][j])
                lowc[j]=cost[p][j];
    }
return ans;
}
View Code

5.kruskal 算法

适用范围：最小生成树MST

算法思想：每次找到最短边，用并查集合并相邻点，直到所有点合并。

代码实现：设置当前集合到其他点的最短路信息集合数组，访问数组，首先将最短路信息设置为任意一点到其他点的距离，之后用最短的一个更新信息。

时间复杂度：O（nlogn)

#include <bits/stdc++.h>
using namespace std;
const int MAXN=110;
const int MAXM=10000;
int F[MAXN];
struct Edge
{
    int u,v,w;
} edge[MAXM];
int tol;
void addedge(int u,int v,int w)
{
    edge[tol].u=u;
    edge[tol].v=v;
    edge[tol++].w=w;
}
bool cmp(Edge a,Edge b)
{
    return a.w<b.w;
}
int find(int x){
    if(x==F[x])return x;
    else return F[x]=find(F[x]);
}
int Kruskal(int n)
{
    memset(F,-1,sizeof(F));
    sort(edge,edge+tol,cmp);
    int cnt=0;//计算加入的边数
    int ans=0;
    for(int i=0; i<tol; i++)
    {
        int u=edge[i].u;
        int v=edge[i].v;
        int w=edge[i].w;
        int t1=find(u);
        int t2=find(v);
        if(t1!=t2)
        {
            ans+=w;
            F[t1]=t2;
            cnt++;
        }
        if(cnt==n-1)
            break;
    }
    if(cnt<n-1)
        return -1;//不连通
    else
        return ans;
}
View Code

6.次小生成树

适用范围：非严格最小生成树

算法思想：首先求出最小生成树，然后求出最小生成树中任意两个节点u，v，u到v的路径上i，j的最大边权，记作MAX[u][v].之后枚举不在最小生成树中的边，将他加入到最小生成树中，则必定出现环，为了去掉环，去掉u到v上的最大边权，更新答案，最小的结果即是答案。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=110;
const int INF=0x3f3f3f3f;
bool vis[MAXN];
int lowc[MAXN];
int pre[MAXN];
int Max[MAXN][MAXN];//Max[i][j] 表示在最小生成树中从 i 到 j 的路径中的最大边权
bool used[MAXN][MAXN];
int Prim(int cost[][MAXN],int n)
{
    int ans=0;
    memset(vis,false,sizeof(vis));
    memset(Max,0,sizeof(Max));
    memset(used,false,sizeof(used));
    vis[0]=true;
    pre[0]=-1;
    for(int i=1; i<n; i++)
    {
        lowc[i]=cost[0][i];
        pre[i]=0;
    }
    lowc[0]=0;
    for(int i=1; i<n; i++)
    {
        int minc=INF;
        int p=-1;
        for(int j=0; j<n; j++)
            if(!vis[j]&&minc>lowc[j])
            {
                minc=lowc[j];
                p=j;

            }
        if(minc==INF)
            return -1;
        ans+=minc;
        vis[p]=true;
        used[p][pre[p]]=used[pre[p]][p]=true;
        for(int j=0; j<n; j++)
        {
            if(vis[j] && j != p)
                Max[j][p]=Max[p][j]=max(Max[j][pre[p]],lowc[p]);
            if(!vis[j]&&lowc[j]>cost[p][j])
            {
                lowc[j]=cost[p][j];
                pre[j]=p;
            }
        }
    }
    return ans;
}
View Code

7.Tarjan算法

适用范围：求解有向图强连通分量

算法思想：dfs，如果顺着某条路线回到原点，那么该路径上所有节点构成一个强连通分块。

代码实现：用栈作为辅助，dfs同时记录下当前节点的访问次序DFN和以当前节点为子树下能找到的最早的访问次序，如果一些节点次序相同，显然为同一强联通块。返回时如果当前的LOW和DFN相同，说明同一连通块内，将这些点从栈中弹出。

时间复杂度：O（N+M）

代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20010;//点数
const int MAXM = 50010;//边数
struct Edge
{
    int to,next;
} edge[MAXM];
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong 数组的值是1 ∼scc
int Index,top;
int scc;//强连通分量的个
bool Instack[MAXN];
int num[MAXN];//各个强连通分量包含点的个数，数组编号 1 ∼ scc
//num 数组不一定需要，结合实际情况
void addedge(int u,int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
void Tarjan(int u)
{
    int v;
    Low[u] = DFN[u] = ++Index;
    Stack[top++] = u;
    Instack[u] = true;
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        v = edge[i].to;
        if( !DFN[v] )
        {
            Tarjan(v);
            if( Low[u] > Low[v] )
                Low[u] = Low[v];
        }
        else if(Instack[v] && Low[u] > DFN[v])Low[u] = DFN[v];
    }
if(Low[u] == DFN[u])
    {
        scc++;
        do
        {
            v = Stack[--top];
            Instack[v] = false;
            Belong[v] = scc;
            num[scc]++;
        }
        while( v != u);
    }
}
void solve(int N)
{
    memset(DFN,0,sizeof(DFN));
    memset(Instack,false,sizeof(Instack));
    memset(num,0,sizeof(num));
    Index = scc = top = 0;
    for(int i = 1; i <= N; i++)
        if(!DFN[i])
            Tarjan(i);
}
void init()
{
    tot = 0;
    memset(head,-1,sizeof(head));
}
View Code

8.Kosaraju算法

适用范围：求解有向图强连通分量

算法思想：dfs，如果顺着某条路线回到原点，那么该路径上所有节点构成一个强连通分块。可以看出，如果按照某个特定顺序进行dfs，dfs的次数就是强联通分量的数目。为了找到这种顺序，首先对图取反，进行逆后序遍历，把结果记入栈中，按栈顶到栈顶正序dfs即可。

代码实现：两边dfs，第一遍，反图，逆后序遍历，第二遍，按栈顺序遍历。

时间复杂度：O（N+M）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20010;
const int MAXM = 50010;
struct Edge
{
    int to,next;
} edge1[MAXM],edge2[MAXM]; //edge1 是原图 G，edge2 是逆图 GT
int head1[MAXN],head2[MAXN];
bool mark1[MAXN],mark2[MAXN];
int tot1,tot2;
int cnt1,cnt2;
int st[MAXN];//对原图进行 dfs，点的结束时间从小到大排序
int Belong[MAXN];//每个点属于哪个连通分量 (0∼cnt2-1)
int num;//中间变量，用来数某个连通分量中点的个数
int setNum[MAXN];//强连通分量中点的个数，编号 0∼cnt2-
void addedge(int u,int v)
{
    edge1[tot1].to = v;
    edge1[tot1].next = head1[u];
    head1[u] = tot1++;
    edge2[tot2].to = u;
    edge2[tot2].next = head2[v];
    head2[v] = tot2++;
}
void DFS1(int u)
{
    mark1[u] = true;    //点的编号从 1 开始
    for(int i = head1[u]; i != -1; i = edge1[i].next)
        if(!mark1[edge1[i].to])
            DFS1(edge1[i].to);
    st[cnt1++] = u;
}
void DFS2(int u)
{
    mark2[u] = true;
    num++;
    Belong[u] = cnt2;
    for(int i = head2[u]; i != -1; i = edge2[i].next)
        if(!mark2[edge2[i].to])
            DFS2(edge2[i].to);
}
void solve(int n)
{
    memset(mark1,false,sizeof(mark1));
    memset(mark2,false,sizeof(mark2));
    cnt1 = cnt2 = 0;
    for(int i = 1; i <= n; i++)
        if(!mark1[i])
            DFS1(i);
    for(int i = cnt1-1; i >= 0; i--)
        if(!mark2[st[i]])
        {
            num = 0;
            DFS2(st[i]);
            setNum[cnt2++] = num;
        }
}
View Code

9.割点与桥

适用范围：求无向图的割点与桥，求双连通分支。

算法思想：求双连通分支：dfs，记录每个节点的访问次序dfn，和子节点最小访问次序low，若出现一个顶点的dfn《它的子节点的low，则该点为割点，若边两个顶点中其中一个点的dfn《另一个点的low，则该边为桥，特别的，根的判断通过是否能一次遍历完所有点判断。

代码实现：

时间复杂度：O（V）

代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10010;
const int MAXM = 100010;
struct Edge
{
    int to,next;
    bool cut;//是否为桥的标记
} edge[MAXM];
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN];
int Index,top;
bool Instack[MAXN];
bool cut[MAXN];
int add_block[MAXN];//删除一个点后增加的连通块
int bridge;
void addedge(int u,int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    edge[tot].cut = false;
    head[u] = tot++;
}
void Tarjan(int u,int pre)
{
    int v;
    Low[u] = DFN[u] = ++Index;
    Stack[top++] = u;
    Instack[u] = true;
    int son = 0;
    int pre_cnt = 0; //处理重边，如果不需要可以去掉
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        v = edge[i].to;
        if(v == pre && pre_cnt == 0)
        {
            pre_cnt++;
            continue;
        }
        if( !DFN[v] )
        {
            son++;
            Tarjan(v,u);
            if(Low[u] > Low[v])
                Low[u] = Low[v];//桥//一条无向边 (u,v) 是桥，当且仅当 (u,v) 为树枝边，且满足DFS(u)<Low(v)
            if(Low[v] > DFN[u])
            {
                bridge++;    //割点
                edge[i].cut = true;
                edge[i^1].cut = true;
            }
//一个顶点 u 是割点，当且仅当满足 (1) 或 (2) (1) u 为树根，且u 有多于一个子树。//(2) u 不为树根，且满足存在 (u,v) 为树枝边 (或称父子边，
//即 u 为 v 在搜索树中的父亲)，使得 DFS(u)<=Low(v)
            if(u != pre && Low[v] >= DFN[u]) //不是树根
            {
                cut[u] = true;
                add_block[u]++;
            }
        }
        else if( Low[u] > DFN[v])
            Low[u] = DFN[v];
    }//树根，分支数大于 1
    if(u == pre && son > 1)
        cut[u] = true;
    if(u == pre)
        add_block[u] = son - 1;
    Instack[u] = false;
    top--;
}
View Code

调用实例：

1）UVA 796 Critical Links 给出一个无向图按顺序输出桥

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10010;
const int MAXM = 100010;
struct Edge
{
    int to,next;
    bool cut;//是否为桥的标记
} edge[MAXM];
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN];
int Index,top;
bool Instack[MAXN];
bool cut[MAXN];
int add_block[MAXN];//删除一个点后增加的连通块
int bridge;
void addedge(int u,int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    edge[tot].cut = false;
    head[u] = tot++;
}
void Tarjan(int u,int pre)
{
    int v;
    Low[u] = DFN[u] = ++Index;
    Stack[top++] = u;
    Instack[u] = true;
    int son = 0;
    int pre_cnt = 0; //处理重边，如果不需要可以去掉
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        v = edge[i].to;
        if(v == pre && pre_cnt == 0)
        {
            pre_cnt++;
            continue;
        }
        if( !DFN[v] )
        {
            son++;
            Tarjan(v,u);
            if(Low[u] > Low[v])
                Low[u] = Low[v];//桥//一条无向边 (u,v) 是桥，当且仅当 (u,v) 为树枝边，且满足DFS(u)<Low(v)
            if(Low[v] > DFN[u])
            {
                bridge++;    //割点
                edge[i].cut = true;
                edge[i^1].cut = true;
            }
//一个顶点 u 是割点，当且仅当满足 (1) 或 (2) (1) u 为树根，且u 有多于一个子树。//(2) u 不为树根，且满足存在 (u,v) 为树枝边 (或称父子边，
//即 u 为 v 在搜索树中的父亲)，使得 DFS(u)<=Low(v)
            if(u != pre && Low[v] >= DFN[u]) //不是树根
            {
                cut[u] = true;
                add_block[u]++;
            }
        }
        else if( Low[u] > DFN[v])
            Low[u] = DFN[v];
    }//树根，分支数大于 1
    if(u == pre && son > 1)
        cut[u] = true;
    if(u == pre)
        add_block[u] = son - 1;
    Instack[u] = false;
    top--;
}

void solve(int N)
{
    memset(DFN,0,sizeof(DFN));
    memset(Instack,false,sizeof(Instack));
    memset(add_block,0,sizeof(add_block));
    memset(cut,false,sizeof(cut));
    Index = top = 0;
    bridge = 0;
    for(int i = 1; i <= N; i++)
        if( !DFN[i] )
            Tarjan(i,i);
    printf("%d␣critical␣links
",bridge);
    vector<pair<int,int> >ans;
    for(int u = 1; u <= N; u++)
        for(int i = head[u]; i != -1; i = edge[i].next)
            if(edge[i].cut && edge[i].to > u)
            {
                ans.push_back(make_pair(u,edge[i].to));
            }
    sort(ans.begin(),ans.end());//按顺序输出桥
    for(int i = 0; i < ans.size(); i++)
        printf("%d␣-␣%d
",ans[i].first-1,ans[i].second-1);
    printf("
");
}
void init()
{
    tot = 0;    //处理重边
    memset(head,-1,sizeof(head));
}
map<int,int>mapit;
inline bool isHash(int u,int v)
{
    if(mapit[u*MAXN+v])
        return true;
    if(mapit[v*MAXN+u])
        return true;
    mapit[u*MAXN+v] = mapit[v*MAXN+u] = 1;
    return false;
}
int main()
{
    int n;
    while(scanf("%d",&n) == 1)
    {
        init();
        int u;
        int k;
        int v;//mapit.clear();
        for(int i = 1; i <= n; i++)
        {
            scanf("%d (%d)",&u,&k);
            u++;//这样加边，要保证正边和反边是相邻的，建无
            while(k--)
            {
                scanf("%d",&v);
                v++;
                if(v <= u)
                    continue;//if(isHash(u,v))continue;
                addedge(u,v);
                addedge(v,u);
            }
        }
        solve(n);
    }
    return 0;
}
View Code

2)POJ 2117 求删除一个点后，图中最多有多少个连通块

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int MAXN = 10010;
  4 const int MAXM = 100010;
  5 struct Edge
  6 {
  7     int to,next;
  8     bool cut;//是否为桥的标记
  9 } edge[MAXM];
 10 int head[MAXN],tot;
 11 int Low[MAXN],DFN[MAXN],Stack[MAXN];
 12 int Index,top;
 13 bool Instack[MAXN];
 14 bool cut[MAXN];
 15 int add_block[MAXN];//删除一个点后增加的连通块
 16 int bridge;
 17 void addedge(int u,int v)
 18 {
 19     edge[tot].to = v;
 20     edge[tot].next = head[u];
 21     edge[tot].cut = false;
 22     head[u] = tot++;
 23 }
 24 void Tarjan(int u,int pre)
 25 {
 26     int v;
 27     Low[u] = DFN[u] = ++Index;
 28     Stack[top++] = u;
 29     Instack[u] = true;
 30     int son = 0;
 31     int pre_cnt = 0; //处理重边，如果不需要可以去掉
 32     for(int i = head[u]; i != -1; i = edge[i].next)
 33     {
 34         v = edge[i].to;
 35         if(v == pre && pre_cnt == 0)
 36         {
 37             pre_cnt++;
 38             continue;
 39         }
 40         if( !DFN[v] )
 41         {
 42             son++;
 43             Tarjan(v,u);
 44             if(Low[u] > Low[v])
 45                 Low[u] = Low[v];//桥//一条无向边 (u,v) 是桥，当且仅当 (u,v) 为树枝边，且满足DFS(u)<Low(v)
 46             if(Low[v] > DFN[u])
 47             {
 48                 bridge++;    //割点
 49                 edge[i].cut = true;
 50                 edge[i^1].cut = true;
 51             }
 52 //一个顶点 u 是割点，当且仅当满足 (1) 或 (2) (1) u 为树根，且u 有多于一个子树。//(2) u 不为树根，且满足存在 (u,v) 为树枝边 (或称父子边，
 53 //即 u 为 v 在搜索树中的父亲)，使得 DFS(u)<=Low(v)
 54             if(u != pre && Low[v] >= DFN[u]) //不是树根
 55             {
 56                 cut[u] = true;
 57                 add_block[u]++;
 58             }
 59         }
 60         else if( Low[u] > DFN[v])
 61             Low[u] = DFN[v];
 62     }//树根，分支数大于 1
 63     if(u == pre && son > 1)
 64         cut[u] = true;
 65     if(u == pre)
 66         add_block[u] = son - 1;
 67     Instack[u] = false;
 68     top--;
 69 }
 70 
 71 void solve(int N)
 72 {
 73     memset(DFN,0,sizeof(DFN));
 74     memset(Instack,0,sizeof(Instack));
 75     memset(add_block,0,sizeof(add_block));
 76     memset(cut,false,sizeof(cut));
 77     Index = top = 0;
 78     int cnt = 0;//原来的连通块数
 79     for(int i = 1; i <= N; i++)
 80         if( !DFN[i] )
 81         {
 82             Tarjan(i,i);//找割点调用必须是 Tarjan(i,i)
 83             cnt++;
 84         }
 85     int ans = 0;
 86     for(int i = 1; i <= N; i++)
 87         ans = max(ans,cnt+add_block[i]);
 88     printf("%d
",ans);
 89 }
 90 void init()
 91 {
 92     tot = 0;
 93     memset(head,-1,sizeof(head));
 94 }
 95 int main()
 96 {
 97     int n,m;
 98     int u,v;
 99     while(scanf("%d%d",&n,&m)==2)
100     {
101         if(n==0 && m == 0)
102             break;
103         init();
104         while(m--)
105         {
106             scanf("%d%d",&u,&v);
107             u++;
108             v++;
109             addedge(u,v);
110             addedge(v,u);
111         }
112         solve(n);
113     }
114     return 0;
115 }
View Code

3)边双连通分支POJ 3177给定一个连通的无向图 G至少要添加几条边才能使其变为双连通图。

去掉桥缩点，再把桥补上就成为一颗树，只要把叶节点个数leaf+1/2就是答案了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5010;//点数
const int MAXM = 20010;//边数，因为是无向图，所以这个值要 *2
struct Edge
{
    int to,next;
    bool cut;//是否是桥标记
} edge[MAXM];
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong 数组的值是1 ∼ block
int Index,top;
int block;//边双连通块数
bool Instack[MAXN];
int bridge;//桥的数
void addedge(int u,int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    edge[tot].cut=false;
    head[u] = tot++;
}
void Tarjan(int u,int pre)
{
    int v;
    Low[u] = DFN[u] = ++Index;
    Stack[top++] = u;
    Instack[u] = true;
    int pre_cnt = 0;
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        v = edge[i].to;
        if(v == pre && pre_cnt == 0)
        {
            pre_cnt++;
            continue;
        }
        if( !DFN[v] )
        {
            Tarjan(v,u);
            if( Low[u] > Low[v] )
                Low[u] = Low[v];
            if(Low[v] > DFN[u])
            {
                bridge++;
                edge[i].cut = true;
                edge[i^1].cut = true;
            }
        }
        else if( Instack[v] && Low[u] > DFN[v]) Low[u] = DFN[v];
    }
if(Low[u] == DFN[u])
    {
        block++;
        do
        {
            v = Stack[--top];
            Instack[v] = false;
            Belong[v] = block;
        }
        while( v!=u );
    }
}
void init()
{
    tot = 0;
    memset(head,-1,sizeof(head));
}
int du[MAXN];//缩点后形成树，每个点的度数
void solve(int n)
{
    memset(DFN,0,sizeof(DFN));
    memset(Instack,false,sizeof(Instack));
    Index = top = block = 0;
    Tarjan(1,0);
    int ans = 0;
    memset(du,0,sizeof(du));
    for(int i = 1; i <= n; i++)
        for(int j = head[i]; j != -1; j = edge[j].next)
            if(edge[j].cut)
                du[Belong[i]]++;
    for(int i = 1; i <= block; i++)
        if(du[i]==1)
            ans++;//找叶子结点的个数 ans, 构造边双连通图需要加边 (ans+1)/2
    printf("%d
",(ans+1)/2);
}
int main()
{
    int n,m;
    int u,v;
    while(scanf("%d%d",&n,&m)==2)
    {
        init();
        while(m--)
        {
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        solve(n);
    }
    return 0;
}
View Code

4）点双连通分支

待补

10.最小树形图

 待补……

11.匈牙利算法（邻接矩阵）

适用范围：已知二分图，寻找二分图最大匹配。

算法思想：dfs寻找增广路，判断由该增广路是否能跟新最大匹配。 因为增广路上在集合中的边和不在集合中的边可以互换，因此就可以通过这种办法更新。

代码实现：对于左边的每一个顶点，找到相邻的未被访问的点或者通过dfs它的配对点来找到它可以匹配的第一个点，计数增加。

时间复杂度O（VE）

代码：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 510;
int uN,vN;
//u,v 的数目，使用前面必须赋值
int g[MAXN][MAXN];//邻接矩阵
int linker[MAXN];
bool used[MAXN];
bool dfs(int u)
{
    for(int v = 0; v < vN; v++)
        if(g[u][v] && !used[v])
        {
            used[v] = true;
            if(linker[v] == -1 || dfs(linker[v]))
        {
            linker[v]= u;
                return true;
            }
        }
    return false;
}
int hungary()
{
    int res = 0;
    memset(linker,-1,sizeof(linker));
    for(int u = 0; u < uN; u++)
    {
        memset(used,false,sizeof(used));
        if(dfs(u))
            res++;
    }
    return res;
}
View Code

邻接表同理，

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5010;//点数的最大值
const int MAXM = 50010;//边数的最大值
struct Edge
{
    int to,next;
} edge[MAXM];
int head[MAXN],tot;
void init()
{
    tot = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
int linker[MAXN];
bool used[MAXN];
int uN;
bool dfs(int u)
{
    for(int i = head[u]; i != -1 ; i = edge[i].next)
    {
        int v = edge[i].to;
        if(!used[v])
        {
            used[v] = true;
            if(linker[v] == -1 || dfs(linker[v]))
            {
                linker[v] = u;
                return true;
            }
        }
    }
    return false;
}
int hungary()
{
    int res = 0;
    memset(linker,-1,sizeof(linker));//点的编号 0∼uN-1
    for(int u = 0; u < uN; u++)
    {
        memset(used,false,sizeof(used));
        if(dfs(u))
            res++;
    }
    return res;
}
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/bestefforts/p/9581129.html