老刘说让我写个图论的总结（一个月前），当时因为在写dp所以推了，今日看尧神在写，不妨补上；
一些模板；
//图论的一些模板；
总结于 2017 3 28，尧神搞完了图论，我跟着写一波总结
/*一个概念;欧拉路
欧拉路也就是一笔画成问题，欧拉路的必要判定条件是每个点的入度为偶数,或者是只有两个点是奇数，
当满足条件2时，这两个点必定一个是起点一个是终点；
/*/
最短路的求法
{
1.
//floyed;
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
for(int u=1;u<=k;u++)
{
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][u]);
}
//（500数据量的求法，基本没用;）
//堆优化的dijkstra
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
typedef pair <int,int> pii;
viod dijkstra(int s){
priority_queue<pii>q;
memset(dis,10,sizeof(dis));
meset(vis,0,sizeof(vis));
d[s]=0;
q.push(make_pair(0,s));
while(!q.empty){
pii tmp=q.top();
q.pop();
int x=tmp.second;
if(vis[x])continue;
vis[x]=1;
for(int i=lin[x];i;i=e[i].next){
if(dis[e[i].y]>dis[x]+e[i].v){
dis[e[i].y]=dis[x]+e[i].v;
q.push(make_pair(e[i].y,x));
}
}
}
}
//判断是否有负环；
//bellman-ford;
//边表存贮；
int bellman-ford(int st){
memset(dis,10,sizeof(dis);
dis[st]=0;
int num=0;
for(int i=1;i<=n;i++){
for(int i=1;i<=sum;i++){
if(dis[a[i].x]+a[i].v<dis[a[i].y])
dis[a[i].y]=dis[a[i].x]+a[i].v,num=1;
if(num==0)return 0;//无负环；
}
return 1；//有负环
}
}
//spfa;
void spfa(int st)
{
memset(dis,10,sizeof(dis));
memset(vis,0,sizeof(vis));
int head=0,tail=1;
while(head<tail)
{
head++;
int x=q[head];
vis[x]=0;
for(int i=lin[q[head]];i;i=e[i].next)
{
int y=e[i].y;
if(dis[x]+e[i].v<dis[y])
{
dis[y]=e[i].v+dis[x];
if(vis[y]==0)
{
vis[y]=1;
q[++tail]=y;
vis[y]=0;
}
}
}
}
}
//最小生成树_边表
//kruskal
int getfather(int k)
{
if(k==father[k])return father[k];
father[k]=getfather(father[k]);
return father[k];
}
void merge(int x,int y);
{
x=getfather(x);
y=getfather(y);
fahter[x]=father[y];
}
int judge(int x,int y)//判断；
{
father[x]=getfather(x);
father[y]=getfather(y);
if(father[x]==father[y])return 1;
return 0;
}
int krskal(int x)
{
for(int i=1;i<=len;i++)
{
int x=e[i].x;
int y=e[i].y;
if(x!=y)
{
merge(x,y);
}
}
}
//topsort 据说是为了确定搜索顺序
void topsort()
{
for(int i=1;i<=n;i++)
{
if(vis[i]==0)
q[++tail]=i;
}
while(head<tail)
{
head++;
int x=q[head];
for(int i=lin[x];i;i=e[i].next)
{
int y=[i].y;
vis[y]--;
if(vis[y]==0)q[++tail]=y;
}
}
}//q 里存的即是topsort序列；
//注意， topsort的序列并不是唯一的，枚举所有的排序情况需要用dfs来存；
// 割边割点与强连通分量；
/* int dfn[10000000],low[10000000];
割点； 所谓割点，即去掉此点后图不连通，那么只需求一下某个点是否能回到比他早的路即可；
*/
trajan(int x,int father)
{
dfn[x]=low[x]=++num;
int son=0;
for(int i=lin[x];i;i=e[i].next)
{
int y=e[i].y;
if(y!=father)
{
if(!dfn[y])
{
trajan(y,x);
if(low[y]<low[x]);
low[x]=low[y],son++;
}
if(dfn[y]<low[x])low[x]=dfn[y],son++;
}
}
if(son==1&&father!=-1||son>=2)
f[x]=1;
}
// 割边；去掉该边后图不连通；
trajan(int x,int fatherlen)
{
dfn[x]=low[x]=++num;
for(int i=lin[x];i;i=e[i].next)
{
int y=e[i].y;
if(i!=fatherlen)
{
if(!dfn[y])
{
trajan(y,x);
if(low[y]<low[x]);
low[x]=low[y];
}
if(dfn[y]<low[x])low[x]=dfn[y];
}
}
if(dfn[x]==low[x])f[fatherlen]=;
}
//强连通分量；
//int tot=0;
//int tnt[10000000];
//int struck[1000000];
//int top=0;
//int bel[10000000];
trajan(int x,int father)
{
dfn[x]=low[x]=++num;
struck[++]
int son=0;
for(int i=lin[x];i;i=e[i].next)
{
int y=e[i].y;
if(!dfn[y])
{
trajan(y,x);
if(low[y]<low[x]);
low[x]=low[y];
}
if(dfn[y]<low[x])low[x]=dfn[y];
}
if(dfn[x]==low[x])
{
tot++;int k;
while(k!=x)
{
k=struck[top--];
tnt[tot]++;
bel[k]=tot;
}
}
}
///*/*/*/*/*/*/*/*/*/*/*/*/*终于写完了（累.....）*/*/*/*/*/*/*/*/*/*/*/*/*/*/*
//*/*/*/*/*/*/*/*/*/*/*/*/*/*好像还有个什么差分约束，过两天再弄吧*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/
}