链式前向星
能够链式遍历以同一个节点为起点的所有边，后加入的先遍历到
变量定义
struct Edge{
int v,w,nex;
}edge[M];
int head[N],cnt;
加边操作
void add(int u,int v,int w){
edge[++cnt].v = v;edge[cnt].w = w;
edge[cnt].nex = head[u];head[u] = cnt;
}
遍历ｕ节点为起点的所有边
for(int i=head[u];i;i=edge[i].nex){
do_something(u,edge[i].v,edge[i].w);
}
一些我不熟悉的概念
- 诱导子图：图Ｇ' 是图Ｇ的诱导子图当且仅当Ｖ(G') 是Ｖ(G) 的一个子集，而Ｅ(G') 是Ｅ(G) 中两个端点都在Ｖ(G')中边的集合
- 独立集：点集中任意两点不相邻，不存在一条边连接独立集中的两个点，任意一条边最多有一个端点在独立集中，大小定义为点的个数（极大独立集、最大独立集）
- |最小顶点覆盖| + |最大独立集| = |Ｖ|
- 团：任意两点都有边连接，大小定义为点的个数（极大团、最大团）
- 支配集：所有无向图中的点，要么属于这个子集，要么与这个子集中的点相邻（极小支配集，最小支配集）
- 最小支配集不一定是独立集，但是最小支配集的大小等于最小的极大独立集
- Ramsey数：对于所有的ｎ个顶点的图，要么包含大小为ｋ的团，要么包含大小为ｌ的独立集。具有这样性质，最小的ｎ称为R(k,l)。对于给定的正整数ｋ,ｌ,R(k,l)的答案唯一且有限，R(3,3) = 6
- 染色：给每个顶点分配一种颜色使得不存在两个相邻的顶点同色
连通性
- 有向图弱连通：仅当每条有向边替换成无向边后是连通的
- 连通度
- 连通性性质
求无向图的割点数（桥数）Ｏ(n+m)
POJ1144 Networks
dfn[u]：DFS遍历过程中，点ｕ是第几个被访问到的
lowlink[u]：DFS遍历对应的DFS树中，以ｕ为根的子树上所有点可以通过某条返祖边（非树边）连向点中dfn的最小值（没有返祖边则为u的dfn）
考察所有点ｕ和它的儿子节点s1,s2...sk;
对于某个si，满足lowlink[si]≥dfn[u] 那么点u是一个割点
对于某个si，满足lowlink[si]>dfn[u] 那么边(u,si)是一个桥
对于搜索树的根节点需要特判一下：如果根有且仅有一个儿子节点，那么根肯定不是割点
int dfs(int now){
dfn[now] = ++cs;
int lowlink = cs,son=0,flag=0,k;
for(int i=head[now];i;i=edge[i].nex){
if(edge[i].v == fa[now]) continue;
if(dfn[edge[i].v])k = dfn[edge[i].v];
else {fa[edge[i].v] = now;k = dfs(edge[i].v);son++;if(k>=dfn[now])flag =1;} // 求桥数 if(k>dfn[now])flag = 1;
lowlink = lowlink<k?lowlink:k;
}
if(!(dfn[now]==1&&son<=1) && flag == 1) ans++;
return lowlink;
}
求双连通分量
UVALive3523
双连通分量：任意两点至少存在两条点不重复的路径
tarjan算法求双连通分量：在上面求割点的代码中，修改部分
int dfs(int now,int fa){
dfn[now] = ++clk;
int lowlink = clk,son=0;
for(int i = head[now];i;i=edge[i].nex){
if(edge[i].v == fa)continue;
if(!dfn[edge[i].v]){
s.push(make_pair(now,edge[i].v));
son++;int k=dfs(edge[i].v,now);
lowlink = lowlink<k?lowlink:k;
if(k>=dfn[now]){
bcc[++bcc_cnt].clear();
while(1){
int u = s.top().first,v=s.top().second;s.pop();
if(book[u]!=bcc_cnt){bcc[bcc_cnt].push_back(u);book[u]=bcc_cnt;}
if(book[v]!=bcc_cnt){bcc[bcc_cnt].push_back(v);book[v]=bcc_cnt;}
if(u==now&&v==edge[i].v) break;
}
}
}
else if(dfn[edge[i].v]<dfn[now]){
s.push(make_pair(now,edge[i].v));
lowlink = lowlink<dfn[edge[i].v]?lowlink:dfn[edge[i].v];
}
}
return lowlink;
}
void find_bcc()
{
for(int i=1;i<=n;i++){
if(!dfn[i]) dfs(i,0);
}
}
求边双连通分量：先做一次dfs标记出所有的桥，然后再做一次dfs 找出边双连通分量。只要保证第二次dfs不经过桥即可
求强连通分量
UVALive 4287 Proving Equivalences
Tarjan算法
在求割点的算法中修改部分
int dfs(int now,int fa){
dfn[now]=++clk;
int lowlink=clk;
s.push(now);
book[now]++;
for(int i=head[now];i;i=edge[i].nex){
if(edge[i].v == fa) continue;
int v = edge[i].v;
if(dfn[v]==0){
int k = dfs(v,now);
lowlink = lowlink<k?lowlink:k;
}
else if(book[v] == 1 &&dfn[v]<lowlink){lowlink = lowlink<dfn[v]?lowlink:dfn[v];}
}
if(dfn[now] == lowlink){
++scc_cnt;
while(!s.empty()){
scc[s.top()]=scc_cnt;
book[s.top()]--;
if(s.top() == now) {s.pop();break;}
s.pop();
}
}
return lowlink;
}
2-SAT
UVALive 3211 Now or later
当条件为 x=xval or y = yval
x' 向 y 连边
y' 向 x 连边
(x' 和x是对偶节点）
代码来源刘汝佳大白书
struct two_sat{
vector<int>G[N<<1];
bool mark[N<<1];
int S[N<<1],c,n;
inline int _(int x){return x<=n?x+n:x-n;}
bool dfs(int x){
if(mark[_(x)]) return false;
if(mark[x]) return true;
mark[x] = true;
S[c++] = x;
for(int i=0;i<G[x].size();i++){
if(!dfs(G[x][i])) return false;
}
return true;
}
void init(int n){
this->n = n;
for(int i = 1;i<=n*2;i++) G[i].clear();
memset(mark,0,sizeof(mark));
}
void add(int x,int xval,int y,int yval){
if(xval == 1) x+=n;
if(yval == 1) y+=n;
G[_(x)].push_back(y);
G[_(y)].push_back(x);
}
bool solve(){
for(int i=1;i<=n;i++)
if(!mark[i]&&!mark[_(i)]){
c =0;
if(!dfs(i)){
while(c>0)mark[S[--c]]=false;
if(!dfs(_(i))) return false;
}
}
return true;
}
};