ACM图论知识总结（持续更新中）

一. 欧拉图

1. 定义：

欧拉图是指通过图（无向图或有向图）中所有边且每边仅通过一次的通路，相应的回路称为欧拉回路 。

2. 性质：

1. 欧拉图均为连通图；
2. 无向连通图 G 是欧拉图，则其不含奇数度结点(所有结点度数均为偶数)；
3. 无向连通图 G 是欧拉通路，则其没有或有两个奇数度的结点，这两个节点为欧拉通路的起点与终点；
4. 有向连通图 D 是欧拉图，则其每个结点的入度=出度；
5. 有向连通图 D 是欧拉通路，则其除起点与终点外，其余每个结点的入度=出度；
6. 上述两点两点均满足：起始点的入度 = 出度 - 1 ，结束点的出度 = 入度 - 1 或 两个点的入度 = 出度（主要针对含有欧拉图或欧拉回路的图）。

3. 代码：

4. 例题：

洛谷P1341 无序字母对

二. 拓扑排序

1. 定义：

在一个有向图中，对所有的节点进行排序，没有一个节点指向它前面的节点。

2. 性质：

1. 图中无环，否则无法进行拓扑排序。

3. 代码：

1. 统计所有节点的入度，将入度为 0 的节点分离出来；
2. 把分离出的节点指向的节点的入度减一；
3. 重复上述操作，直到所有的节点都被分离出来；
4. 如果最后不存在入度为 0 的节点，说明有环，不存在拓扑排序，即无解。

#include<bits/stdc++.h>
using namespace std;
vector<int>edge[30];//邻接表
int in[30];//记录入度
set<int>mmp;//标记
int main()
{
    int s1,s2;
    while(cin>>s1>>s2)
    {
        mmp.insert(s1);
        mmp.insert(s2);//标记图中记录的点
        in[s2]++;//记录入度
        edge[s1].push_back(s2);//记录邻接表
    }
    priority_queue<int,vector<int>,greater<int> >ans;//大部分题目要求将拓扑序列按照字典序最小的情况输出，故需要用到优先队列来处理
    for(int i=0;i<30;i++)//入度为0的点入队
        if(in[i]==0&&mmp.count(i)!=0)
            ans.push(i);
    queue<int>Count;//记录出队顺序以及数量
    while(!ans.empty())
    {
        int flag=ans.top();
        ans.pop();//入度为0的点出队
        Count.push(flag);//按顺序入队
        for(int i=0;i<edge[flag].size();i++)//将该点所发出的边去掉
        {
            in[edge[flag][i]]--;
            if(in[edge[flag][i]]==0&&mmp.count(edge[flag][i])!=0)//如果有点的入度更新为0，则入优先队列
                ans.push(edge[flag][i]);
        }
    }
    if(Count.size()==mmp.size())//判断是否有环
        while(!Count.empty())
        {
            cout<<Count.front();
            Count.pop();
        }
    else cout<<"No Answer!";//有环的输出
    return 0;
}

4. 例题：

2153: D.ly的排队问题