【OI】关于一些图论
这篇文章其实是两年前写的，因为数据未妥善保存才导致现在进行复提。
强连通分量
我们可以用 tarjan 来求
具体见代码，主要怕以后忘了对塔尖的深度的理解才写这篇blog。
具体细节见注释。
例题：P2341 [USACO03FALL][HAOI2006]受欢迎的牛 G
/*
1.dfn，表示这个点在dfs时是第几个被搜到的。
2.low, 表示这个点以及其子孙节点连的所有点中dfn最小的值
3.stack, 表示当前所有可能能构成是强连通分量的点。
4.vis, 表示一个点是否在stack数组中。
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 50001;
int n,m,dfn[N],low[N],vis[N],color[N], c[N], head[N],n_m[N],top,num,sum,tot,stack[N];
struct Edge
{
int to,next;
};
Edge e[N];
void add(int a, int b)
{
e[++tot].to=b;
e[tot].next=head[a];
head[a]=tot;
}
void tarjan(int u)
{
low[u]=dfn[u]=++sum;//初始化，在开始时先使low[i]=dfn[i]
stack[++top]=u; vis[u] = 1;//初始化
for (int i=head[u]; i; i=e[i].next)
{
int v=e[i].to;
if (dfn[v]) {if (vis[v]) low[u]=min(low[v],low[u]); }
else tarjan(v),low[u]=min(low[v],low[u]);
}//遍历每个点，如果已经被搜到过了，就看它是否在stack中，如若是，则取min；没被搜到过就搜这个点，再取min
if (low[u]==dfn[u])//如果找到一个强连通分量
{
color[u]=++num; vis[u] = 0; c[num]= 1;//color将该强连通分量中所有点染成同色，c[i]表示这个强连通分量中有几个数
while (stack[top]!=u)
{
c[num]++;
vis[stack[top]] = 0;
color[stack[top]]=num;
--top;
}//将该强连通分量找完为止
--top;
}
}
int main()
{
cin >> n >> m;
int a,b;
for (int i=1; i<=m; i++) cin >> a >> b,add(a,b);//建边
for (int i=1; i<=n; i++)
if (!dfn[i]) tarjan(i);//如果这个点还没有被搜到，那就对该点进行操作
for (int i=1; i<=n; i++)
for (int j=head[i]; j; j=e[j].next)
{
if (color[i]!=color[e[j].to]) n_m[color[i]]++;
}//遍历每个点，并统计出度
int ans=0,u=0;
for (int i=1; i<=num; i++) if (!n_m[i]) ans=c[i],u++;
// cout << u << endl;
if (u==1) cout << ans;
else cout << 0;
return 0;
}
关于欧拉图
通过图（无向图或有向图）中所有边且每边仅通过一次通路，这条路径称为欧拉路径，而相应的回路称为欧拉回路，具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。
某些定理
无向连通图 是欧拉图，当且仅当 不含奇数度结点( 的所有结点度数为偶数)；
无向连通图 含有欧拉通路，当且仅当 有零个或两个奇数度的结点；
有向连通图 是欧拉图，当且仅当该图为连通图且 中每个结点的入度=出度；
有向连通图 含有欧拉通路，当且仅当该图为连通图且 中除两个结点外，其余每个结点的入度=出度，起始点 的入度=出度-1，结束点 的出度=入度-1 或两个点的入度=出度；
一个非平凡连通图是欧拉图当且仅当它的每条边属于奇数个环；
整理得某些判定方法
（以下图均视为连通图）
若一个图存在欧拉路径，当且仅当
无向图：
有且只有两个点度数为奇数；
其余所有点度数为偶数。
有向图
有一个点入度比出度大 1 ，一个点出度比入度大 1；
其余所有点的入度等于出度。
若一个图存在欧拉回路，当且仅当
无向图的所有顶点的度数都是偶数；
有向图的所有顶点的入度与出度都相等。
具体做法
在此介绍
Hierholzer 算法
该算法的思路是，先找一个顶点然后一直搜与它相连的点，直到搜不到为止（即出现环），然后再从从没搜过的点开始搜，直到所有的边都被访问过。
例题：[USACO3.3]骑马修栅栏 Riding the Fences
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
const int N =501;
const int M = 1111;
int n,m,du[M],vis[N][N],op;
vector <int > e[M];
stack <int> s;//栈，记录经过的节点。
void dfs(int u)
{
for (int i=0; i<e[u].size(); i++)
{
int v=e[u][i];
if (vis[u][v])
{
vis[u][v]--;
vis[v][u]--;
dfs(v);
}
}
s.push(u);
}
int main()
{
cin >> m;
int maxx=0,minn=1e9;
for (int i=1; i<=m; i++)
{
int u,v;
cin >> u >> v;
du[u]++;
du[v]++;
vis[u][v]++;
vis[v][u]++;
e[u].push_back(v);
e[v].push_back(u);
// maxx=max(u,max(v,maxx));
minn=min(minn,min(u,v));
}
op=minn;
for (int i=minn; i<=m; i++)
sort(e[i].begin(),e[i].end());//vector内排序
for (int i=minn; i<=m; i++)
if (du[i]%2)//奇度节点
{
op=i;//顶点
break;
}
// cout << op << endl;
dfs(op);
while(!s.empty())
{
printf("%d\n",s.top());
s.pop();
}
return 0;
}
关于拓扑排序
这么写容易理解但效率低
//b[]为每个点的入度
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(b[j]==0){ //找到一个入度为0的点
ans=j;
vis[cnt++]=j;
b[j]--;
break;
}
}
for(j=1;j<=n;j++)
if(a[ans][j]) b[j]--; //与入度为0的点相连的点的入度减一
}
printf("%d",vis[0]);
for(i=1;i<cnt;i++) printf(" %d",vis[i]);
效率更高的方法：
void topo()
{
for(int i=1; i<=n; i++)
if(indeg[i]==0)
q.push(i);
while(!q.empty())
{
const int u=q.front();
ans[++cnt]=u;
q.pop();
for(int i=1; i<=n; i++)
if(a[u][i])
{
indeg[i]--;
if(indeg[i]==0)
q.push(i);
}
}
}
//很好理解...
例题：P4017 最大食物链计数
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 5001;
const int mod = 80112002;
int n,m,a[N][N],ru[N],ans,cnt,chu[N],f[N];
queue<int > q;
void topo()
{
for(int i=1; i<=n; i++)
if(ru[i]==0)
q.push(i),f[i]=1;
while(!q.empty())
{
int u=q.front();
// ans[++cnt]=u;
q.pop();
for(int i=1; i<=n; i++)
if(a[u][i])
{
f[i]=(f[i]+f[u])%mod;
ru[i]--;
if(ru[i]==0&&chu[i]==0)
{
ans=(ans+f[i])%mod;
continue;
}
if(ru[i]==0)
q.push(i);
}
}
}
int main()
{
cin >> n >> m;
for (int i=1; i<=m; i++)
{
int u,v;
cin >> u >> v;
a[u][v]++;
ru[v]++;
chu[u]++;
}
topo();
cout << ans;
}
关于最小生成树
有 kruskal 和 prim 两种算法
前：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n,m,fa[N],cnt,ans,u1,v1;
struct Edge
{
int u,v,w;
};
Edge e[N];
bool cmp(Edge x, Edge y)
{
return x.w<y.w;
}
int find(int x)
{
while (x!=fa[x]) x=fa[x]=fa[fa[x]];
return x;
}
void kruskal()
{
sort(e+1,e+m+1,cmp);
for (int i=1; i<=m; i++)
{
u1=find(e[i].u),v1=find(e[i].v);
if (u1==v1) continue;
ans+=e[i].w;
fa[v1]=u1;
if (++cnt==n-1) break;
}
}
int main()
{
cin >> n >> m;
for (int i=1; i<=n; i++) fa[i]=i;
for (int i=1; i<=m; i++)
cin >> e[i].u >> e[i].v >> e[i].w;
kruskal();
cout << ans;
return 0;
}
