今天进入图论的学习。图论只考察初试学过的算法，一般都是模版题。常见考点有图相关的数据结构——邻接表法，图的遍历 BFS DFS 并查集，单源最短路径迪杰斯特拉。图由顶点和边构成，度用来说明该顶点邻接边的数量情况。权值说明了边的长度情况。邻接表法使用动态数组模拟链表。下面是最简单的一个邻接表。
#include <stdio.h>
#include <vector>
using namespace std;
// A-B A-C A-D C-D
int main(){//A-0 B-1 C-2 D-3vector<int> graph[4];int u, v;u=0, v=1;graph[u].push_back(v);graph[v].push_back(u);u=0, v=2;graph[u].push_back(v);graph[v].push_back(u);u=0, v=3;graph[u].push_back(v);graph[v].push_back(u);u=2, v=3;graph[u].push_back(v);graph[v].push_back(u);}对于不相交的集合，做find，根据元素找到所在的集合，Union对多个集合进行合并。用树管理每一个集合。Find(x,y)，x找到祖先，y找到祖先判断祖先是否相同。Union将一棵树加入另一棵树作为子树。树的构建容易变成一个链表，采取压缩路径的方法，下面是一个简单的并查集。
#include <stdio.h>
#include <vector>
using namespace std;
int father[1000];
//i 数组下标是集合数据编号 father[i]保存集合数据父亲的编号
//根i father[i] = i
void InitDisjointset(int n){//0~n-1for(int i = 0; i<n;i++){father[i] = i;}
}
int FindDisjointSet(int u){if(u == father[u]) return u;else {father[u] = FindDisjointSet(father[u]);return father[u];//路径压缩}
}
void UnionDisjointSet(int u, int v){int uroot = FindDisjointSet(u);int vroot = FindDisjointSet(v);father[vroot] = uroot;
}
int main(){//1 2 3 4 //5 6 7//0 8 int n = 9;InitDisjointset(n);UnionDisjointSet(1, 2);UnionDisjointSet(1, 3);UnionDisjointSet(1, 4);UnionDisjointSet(5, 6);UnionDisjointSet(5, 7);UnionDisjointSet(0, 8);for(int i = 0; i < 8;i++){printf("%d", father[i]);}
}第一题是畅通工程。拿下。
#include <stdio.h>
#include <vector>
using namespace std;
int father[1000];
int Find(int u) {if (u == father[u]) return u;else {father[u] = Find(father[u]);return father[u];}
}
void Union(int u, int v) { //下标大的合并到下标小的int uroot = Find(u);int vroot = Find(v);father[vroot] = uroot;
}
int main() {int N, M;while (scanf("%d%d", &N, &M) != EOF) {//城镇从1到N M条路if (N == 0) break;for (int i = 1; i <= N; i++) {father[i] = i;}//初试化并查集for (int i = 0; i < M; i++) {int u, v;scanf("%d%d", &u, &v);if (u < v) {Union(u, v);} else Union(v, u);}int res = 0;for (int i = 1; i <= (N); i++) {if (father[i] == i) res++;}printf("%d\n", res - 1);}
}第二题是这是一棵树吗。首先树不存在入度大于2的节点，已连通的uv不应当有新边在加入，同时输入完成后应当是一个连通图，边数 = 顶点数减1。挺复杂的一道题。
#include <stdio.h>
#include <vector>
using namespace std;
int father[10001];
int Find(int u){if(u == father[u]) return u;else {father[u] = Find(father[u]);return father[u];}
}
void Union(int u, int v){int uroot = Find(u);int vroot = Find(v);father[vroot] = uroot;
}
void Initset(int n ){for(int i = 0; i<n;i++){father[i] = i;}
}
int main(){int u, v;Initset(10001);int casenum = 1;int edgeCount = 0;int vertexCount = 0;vector<int> vertex(10001);//vertex[i] = 0说明i没出现过vector<int> indegree(10001);//记录i号节点入度bool istree = true;while(1){scanf("%d%d", &u, &v);if(u == -1&& v==-1) break;else if(u == 0&& v == 0){//一个图已经记录好了if(vertexCount != edgeCount+1){istree = false;//有特例，空树}if(vertexCount == 0&&edgeCount == 0) istree = true;if(istree == true){printf("Case %d is a tree.\n", casenum);}else printf("Case %d is not a tree.\n", casenum);//重置casenum++;Initset(10001);edgeCount = 0;vertexCount = 0;for(int i = 0; i<10001;i++){vertex[i] = 0;indegree[i] = 0;}istree = true;}else{//往当前图里加入新边edgeCount++;if(vertex[u] == 0){vertex[u] = 1;vertexCount++;}if(vertex[v] == 0){vertex[v] = 1;vertexCount++;}if(Find(u) == Find(v)){//判断是否成环istree = false;}else Union(u, v);indegree[v]++;if(indegree[v]>1) istree=false;}}
}第三题是连通图。
#include <stdio.h>
using namespace std;
int father[1001];
int find(int u) {if (u == father[u]) return u;else {father[u] = find(father[u]);return father[u];}
}
void Union(int u, int v) {int uroot = find(u);int vroot = find(v);father[vroot] = uroot;
}
int main() {int n, m;while (scanf("%d%d", &n, &m) != EOF) {if (n == 0) break;for (int i = 1; i <= n; i++) {father[i] = i;}for (int i = 0; i < m; i++) {int u, v;scanf("%d%d", &u, &v);Union(u, v);}int res = 0;for (int i = 1; i <= n; i++) {if (i == father[i]) res++;}if (res > 1) printf("NO\n");else printf("YES\n");}
}第四题是第一题。好奇怪的名字。第一次没有使用大树合并小数，导致产生了段错误。
#include <stdio.h>
using namespace std;
int father[1000];
int visited[1000];
int find(int u){if(u == father[u]) return u;else{father[u] = find(father[u]);return father[u];}
}
void Union(int u, int v){int uroot = find(u);int vroot = find(v);father[vroot] = uroot;
}
int main(){for(int i = 0;i<1000;i++){father[i] = i;visited[i] = 0;}int u,v;while(scanf("%d%d", &u, &v)!=EOF){Union(u, v);visited[u] = 1;visited[v] = 1;}int res = 0;for(int i =0;i<1000;i++){if(i == father[i]&&visited[i]==1) res++;}printf("%d", res);
}结果发现单纯数组开小了，难绷。
#include <stdio.h>
using namespace std;
const int maxN = 1e6;
int father[maxN];
int visited[maxN];
int find(int u){if(u == father[u]) return u;else{father[u] = find(father[u]);return father[u];}
}
void Union(int u, int v){int uroot = find(u);int vroot = find(v);father[vroot] = uroot;
}
int main(){for(int i = 0;i<maxN;i++){father[i] = i;visited[i] = 0;}int u,v;while(scanf("%d%d", &u, &v)!=EOF){Union(u, v);visited[u] = 1;visited[v] = 1;}int res = 0;for(int i =0;i<maxN;i++){if(i == father[i]&&visited[i]==1) res++;}printf("%d", res);
}第五题是找出直系亲属。不太会写。拼尽全力无法战胜。
#include <iostream>#include <cstdio>using namespace std;const int MAXN = 30;int children[MAXN];int Generation(int x, int y) {int level;level = 0;int a = x;while (children[a] != a) {a = children[a];level++;if (a == y) {return level;}}level = 0;int b = y;while (children[b] != b) {b = children[b];level--;if (b == x) {return level;}}return 0;}string Relationship(int level) {string answer;if (level == 0) {answer = "-";} else if (level == 1) {answer = "parent";} else if (level == 2) {answer = "grandparent";} else if (level > 2) {for (int j = 0; j < level - 2; ++j) {answer += "great-";}answer += "grandparent";} else if (level == -1) {answer = "child";} else if (level == -2) {answer = "grandchild";} else if (level < -2) {for (int j = 0; j < -2 - level; ++j) {answer += "great-";}answer += "grandchild";}return answer;}int main() {int n, m;while (scanf("%d%d", &n, &m) != EOF) {for (int i = 0; i < MAXN; ++i) {children[i] = i;}for (int i = 0; i < n; ++i) {char child, father, mother;cin >> child >> father >> mother;if (father - 'A' != '-') {children[father - 'A'] = child - 'A';}if (mother - 'A' != '-') {children[mother - 'A'] = child - 'A';}}for (int i = 0; i < m; ++i) {char guy1, guy2;cin >> guy1 >> guy2;int level = Generation(guy1 - 'A', guy2 - 'A');cout << Relationship(level) << endl;}}return 0;}