graph.cpp

ACM经典算法ACM经典算法ACM经典算法

/*============================================================*\
 | DAG的深度优先搜索标记                                      |
 | INIT: edge[][]邻接矩阵; pre[], post[], tag全置0;           |
 | CALL: dfstag(i, n);                                        |
\*============================================================*/
int edge[V][V], pre[V], post[V], tag;
void dfstag(int cur, int n)                  // vertex: 0 ~ n-1
{
	pre[cur] = ++tag;
	for (int i=0; i<n; ++i) if (edge[cur][i]) {
		if (0 == pre[cur]) {
			printf("Tree Edge!\n");
			dfstag(i, n);
		}
		else {
			if (0 == post[i]) printf("Back Edge!\n");
			else if (pre[i] > pre[cur]) printf("Down Edge!\n");
			else printf("Cross Edge!\n");
		}
	}
	post[cur] = ++tag;
}
/*============================================================*\
 | 无向图找桥                                                 |
 | INIT: edge[][]邻接矩阵; vis[], pre[], anc[], bridge 置为0  |
 | CALL: dfs(0, -1, 1, n);                                    |
\*============================================================*/
int bridge, edge[V][V], anc[V], pre[V], vis[V];
void dfs(int cur, int father, int dep, int n)// vertex: 0 ~ n-1
{
	if (bridge) return;
	vis[cur] = 1; pre[cur] = anc[cur] = dep;
	for (int i=0; i<n; ++i) if (edge[cur][i]) {
		if (i != father && 1 == vis[i]) {
			if (pre[i] < anc[cur]) anc[cur] = pre[i];//back edge
		}
		if (0 == vis[i]) {	                         //tree edge
			dfs(i, cur, dep+1, n);
			if (bridge) return;
			if (anc[i] < anc[cur]) anc[cur] = anc[i];
			if (anc[i] > pre[cur]) { bridge = 1; return; }
		}
	}
	vis[cur] = 2;
}
/*============================================================*\
 | 无向图连通度(割)                                           |
 | INIT: edge[][]邻接矩阵; vis[], pre[], anc[], deg[]置为0    |
 | CALL: dfs(0, -1, 1, n);                                    |
\*============================================================*/
int edge[V][V], anc[V], pre[V], vis[V], deg[V];
void dfs(int cur, int father, int dep, int n)// vertex: 0 ~ n-1
{
	int cnt = 0;
	vis[cur] = 1; pre[cur] = anc[cur] = dep;
	for (int i=0; i<n; ++i) if (edge[cur][i]) {
		if (i != father && 1 == vis[i]) {
			if (pre[i] < anc[cur]) anc[cur] = pre[i];//back edge
		}
		if (0 == vis[i]) {                           //tree edge
			dfs(i, cur, dep+1, n);
			++cnt;
			if (anc[i] < anc[cur])	anc[cur] = anc[i];
			if ((cur==0 && cnt>1) || (cnt!=0 && anc[i]>=pre[cur]))
				++deg[cur];            // link degree of a vertex
		}
	}
	vis[cur] = 2;
}
/*============================================================*\
 | 拓扑排序                                                   |
\*============================================================*/
1.	call DFS to compute finish times f[v] for each vertex v.
2.	as each vertex is finished,
	insert it onto the front of a linked list.
3.	return the linked list of vertices.
/*============================================================*\
 | 最大团问题 DP + DFS                                        |
 | INIT: g[][]邻接矩阵;                                       |
 | CALL: res = clique(n);                                     |
\*============================================================*/
int g[V][V], dp[V], stk[V][V], mx;
int dfs(int n, int ns, int dep)
{
	if (0 == ns) {
		if (dep > mx) mx = dep;
		return 1;
	}
	int i, j, k, p, cnt;
	for (i = 0; i < ns; i++) {
		k = stk[dep][i]; cnt = 0;
		if (dep + n - k <= mx) return 0;
		if (dep + dp[k] <= mx) return 0;
		for (j = i + 1; j < ns; j++) {
			p = stk[dep][j];
			if (g[k][p]) stk[dep + 1][cnt++] = p;
		}
		dfs(n, cnt, dep + 1);
	}
	return 1;
}
int clique(int n)
{
	int i, j, ns;
	for (mx = 0,  i = n - 1; i >= 0; i--) { // vertex: 0 ~ n-1
		for (ns = 0, j = i + 1; j < n; j++)
			if (g[i][j]) stk[1][ ns++ ] = j;
		dfs(n, ns, 1); dp[i] = mx;
	}
	return mx;
}
/*============================================================*\
 | O(E)输出欧拉路径                                           |
 | INIT: adj[][]置为图的邻接表; cnt[a]为a点的邻接点个数;      |
 | CALL: elpath(0);                                           |
\*============================================================*/
int adj[V][V], idx[V][V], cnt[V], stk[V], top;
int path(int v)
{
	for (int w ; cnt[v] > 0; v = w) {
		stk[ top++ ] = v;
		w = adj[v][ --cnt[v] ];
		adj[w][ idx[v][w] ] = adj[w][ --cnt[w] ];
	}
	return v;
}
void elpath (int b, int n)          // begin from b
{
	int i, j;
	for (i = 0; i < n; ++i)         // vertex: 0 ~ n-1
		for (j = 0; j < cnt[i]; ++j)
			idx[i][ adj[i][j] ] = j;
	printf("%d", b);
	for (top = 0; path(b) == b && top != 0; ) {
		b = stk[ --top ];
		printf("-%d", b);
	}
	printf("\n");
}
/*============================================================*\
 | Dijkstra O(E * log E)                                      |
 | INIT: 调用init(nv, ne)读入边并初始化;                      |
 | CALL: dijkstra(n, src); dist[i]为src到i的最短距            |
\*============================================================*/
#define typec int                          // type of cost
const typec inf = 0x3f3f3f3f;              // max of cost
typec cost[E], dist[V];
int e, pnt[E], nxt[E], head[V], prev[V], vis[V];
struct qnode {
	int v; typec c;
	qnode (int vv = 0, typec cc = 0) : v(vv), c(cc) {}
	bool operator < (const qnode& r) const { return c>r.c; }
};
void dijkstra(int n, const int src)
{
	qnode mv;
	int i, j, k, pre;
	priority_queue<qnode> que;
	vis[src] = 1; dist[src] = 0;
	que.push(qnode(src, 0));
	for (pre = src, i=1; i<n; i++) {
		for (j = head[pre]; j != -1; j = nxt[j]) {
			k = pnt[j];
			if (vis[k] == 0 && dist[pre] + cost[j] < dist[k]) {
				dist[k] = dist[pre] + cost[j];
				que.push(qnode(pnt[j], dist[k]));
				prev[k] = pre;
			}
		}
		while (!que.empty() && vis[que.top().v] == 1) que.pop();
		if (que.empty()) break;
		mv = que.top(); que.pop();
		vis[pre = mv.v] = 1;
	}
}
inline void addedge(int u, int v, typec c)
{
	pnt[e] = v; cost[e] = c; nxt[e] = head[u]; head[u] = e++;
}
void init(int nv, int ne)
{
	int i, u, v; typec c;
	e = 0;
	memset(head, -1, sizeof(head));
	memset(vis, 0, sizeof(vis));
	memset(prev, -1, sizeof(prev));
	for (i = 0; i < nv; i++) dist[i] = inf;
	for (i = 0; i < ne; ++i) {
		scanf("%d%d%d", &u, &v, &c); // %d: type of cost
		addedge(u, v, c);            // vertex: 0 ~ n-1, 单向边
	}
}
/*============================================================*\
 | Dijkstra O(E * log V)                                      |
 | INIT: 调用init(nv, ne)读入边并初始化;                      |
 | CALL: dijkstra(src); dist[i]为src到i的最短距               |
\*============================================================*/
#define typec int                          // type of cost
const typec inf = 0x3f3f3f3f;              // max of cost
struct edge { int adj, nxt; typec cost; } eg[E];
int n, e, head[V], path[V], hp[V], idx[V], sz;
typec dist[V];
void fixdown(int i)
{
    int j, tx;
    for (tx = hp[i]; 2 * i + 1 < sz; i = j) {
        j = 2 * i + 1;
        if (j + 1 < sz && dist[ hp[j+1] ] < dist[ hp[j] ]) ++j;
        if (dist[hp[j]] >= dist[tx]) break;
        idx[ hp[i] = hp[j] ] = i;
    }
    idx[ hp[i] = tx ] = i;
}
void fixup(int i)
{
    int j, tx;
    for (tx = hp[i]; i > 0; i = j) {
        j = (i - 1) / 2;
        if(dist[ hp[j] ] <= dist[ tx ]) break;
        idx[ hp[i] = hp[j] ] = i;
    }
    idx[ hp[i] = tx ] = i;
}
void dijkstra(int src) {
	int i, v, id;
    dist[src] = 0; idx[src] = 0; hp[0] = src; sz = 1;
    while (sz > 0) {
        idx[ id = hp[0] ] = -2;
        idx[ hp[0] = hp[--sz] ] = 0;
        fixdown(0);
        for (i = head[id]; i != -1; i = eg[i].nxt) {
			if (idx[v = eg[i].adj] != -2) {
				if (dist[id] + eg[i].cost < dist[v]) {
					dist[v] = dist[id] + eg[i].cost;
					path[v] = i;
					if (idx[v] == -1) {
						hp[sz] = v;
						idx[v] = sz++;
						fixup(sz-1);
					}
					else fixup(idx[v]);
				}
			}
        }
    }
}
void addedge(int u, int v, typec c)
{
    eg[e].adj = v; eg[e].cost = c;
    eg[e].nxt = head[u]; head[u] = e++;
}
void init(int nv, int ne)
{
	int i, u, v; typec c;
	n = nv; e = 0;
	memset(head, -1, sizeof(head));
	memset(idx, -1, sizeof(idx));
	memset(path, -1, sizeof(path));
	for (i = 0; i < nv; i++) dist[i] = inf;
	for (i = 0; i < ne; ++i) {
		scanf("%d%d%d", &u, &v, &c); // %d: type of cost
		addedge(u, v, c);            // vertex: 0 ~ n-1, 单向边
	}
}
/*============================================================*\
 | BellmanFord单源最短路                                      |
 | INIT: edge[E][3]为边表                                     |
 | CALL: bellman(src); 若有负圈返回0; dist[i]为src到i的最短距 |
\*============================================================*/
#define typec int                      // type of cost
const typec inf=0x3f3f3f3f;            // max of cost
int n, m, pre[V], edge[E][3];
typec dist[V];
int relax (int u, int v, typec c)
{
	if (dist[v] > dist[u] + c) {
		dist[v] = dist[u] + c;
		pre[v] = u; return 1;
	}
	return 0;
}
int bellman (int src)
{
	int i, j;
	for (i=0; i<n; ++i) {
		dist[i] = inf; pre[i] = -1;
	}
	dist[src] = 0;
	for (i=1; i<n; ++i) for (j=0; j<m; ++j) {
		relax(edge[j][0], edge[j][1], edge[j][2]);
	}
	for (j=0; j<m; ++j) {
		if (1 == relax(edge[j][0], edge[j][1], edge[j][2]))
			return 0;                 // 有负圈
	}