挑战程序设计竞赛 算法和数据结构 第12章 图
挑战程序设计竞赛 算法和数据结构 第12章 图
12.2 图的表示
ALDS1_11_A:Graph
原书AC代码：
//ALDS1_11_A:Graph
#include <iostream>
using namespace std;
static const int N = 100;
int main(){
int M[N][N];//0 0起点的邻接矩阵
int n,u,k,v;
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)M[i][j]=0;
}
for(int i=0;i<n;i++){
cin>>u>>k;
u--;//转换为0起点
for(int j=0;j<k;j++){
cin>>v;
v--;//转换为0起点
M[u][v]=1;//1 本人此处写成M[v][v]=1; 在u和v之间画出一条边
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(j)cout<<" ";
cout<<M[i][j];
}
cout<<endl;
}
return 0;
}
这次没有仿照上述代码，本人未看书，直接编写的C语言AC代码如下：
//ALDS1_11_A:Graph
//提交，Presentation Error,明白格式要求比较高 ,修改格式后，提交AC 2017-9-29
#include <stdio.h>
#include <string.h>
int a[110][110];
int main(){
int n,u,k,v,i,j;
memset(a,0,sizeof(0));
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d%d",&u,&k);
for(j=1;j<=k;j++){
scanf("%d",&v);
a[u][v]=1;
}
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(j==1)//1漏了该if语句
printf("%d",a[i][j]);//1漏了该功能
else
printf(" %d",a[i][j]);
}
printf("\n");
}
return 0;
}
该题，感觉比较新颖，加深了对邻接表与邻接矩阵的理解。
12.3 深度优先搜索
ALDS1_11_B:Depth First Search
看了样例的图，感觉耳目一新，该题对深度优先遍历的理解大有帮助，样例图如下：
原书AC代码：
方法一
//ALDS1_11_B:Depth First Search
//C(用递归实现的深度优先搜索)
#include <stdio.h>
#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2
int n,M[N][N];
int color[N],d[N],f[N],tt;
//用递归函数实现的深度优先搜索
void dfs_visit(int u){
int v;
color[u]=GRAY;
d[u]=++tt;//最初的访问
for(v=0;v<n;v++){
if(M[u][v]==0)continue;
if(color[v]==WHITE){
dfs_visit(v);
}
}
color[u]=BLACK;
f[u]=++tt;//访问结束
}
void dfs(){
int u;
//初始化
for(u=0;u<n;u++)color[u]=WHITE;
tt=0;
for(u=0;u<n;u++){
//以未访问的u为起点进行深度优先搜索
if(color[u]==WHITE)dfs_visit(u);
}
for(u=0;u<n;u++){
printf("%d %d %d\n",u+1,d[u],f[u]);
}
}
int main(){
int u,v,k,i,j;
scanf("%d",&n);
for(i=0;i<n;i++){
for(j=0;j<n;j++)M[i][j]=0;
}
for(i=0;i<n;i++){
scanf("%d %d",&u,&k);
u--;
for(j=0;j<k;j++){
scanf("%d",&v);
v--;
M[u][v]=1;
}
}
dfs();
return 0;
}
方法二：
//ALDS1_11_B:Depth First Search
//C++(用栈实现的深度优先搜索)
#include <iostream>
#include <stack>
using namespace std;
static const int N = 100;
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;
int n,M[N][N];
int color[N],d[N],f[N],tt;
int nt[N];
//按编号顺序获取与u相邻的v
int next(int u){
for(int v=nt[u];v<n;v++){
nt[u]=v+1;
if(M[u][v])return v;
}
return -1;
}
void dfs_visit(int r){
for(int i=0;i<n;i++) nt[i]=0;
stack<int> S;
S.push(r);
color[r]=GRAY;
d[r]=++tt;
while(!S.empty()){
int u=S.top();
int v=next(u);
if(v!=-1){
if(color[v]==WHITE){
color[v]=GRAY;
d[v]=++tt;
S.push(v);
}
}else{
S.pop();
color[u]==BLACK;
f[u]=++tt;
}
}
}
void dfs(){
//初始化
for(int i=0;i<n;i++){
color[i]=WHITE;
nt[i]=0;
}
tt=0;
//以未访问的u为起点进行深度优先搜索
for(int u=0;u<n;u++){
if(color[u]==WHITE)dfs_visit(u);
}
for(int i=0;i<n;i++){
cout<<i+1<<" "<<d[i]<<" "<<f[i]<<endl;
}
}
int main(){
int u,k,v;
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)M[i][j]=0;
}
for(int i=0;i<n;i++){
cin>>u>>k;
u--;
for(int j=0;j<k;j++){
cin>>v;
v--;
M[u][v]=1;
}
}
dfs();
return 0;
}
这次没有仿照上述代码，本人未看书，直接编写的C语言AC代码如下：
该题是有向图，时间戳可以开一个全局变量进行计数。
在考虑是用转成邻接矩阵，还是直接用邻接表，思考过后，为了提升能力，还是采用邻接表，采用dfs方式进行处理。
//ALDS1_11_B:Depth First Search
//因所掌握的邻接表存储方式，编写了一通，与该题遍历顺序不一致，故改成邻接矩阵表示法
//样例通过，提交WA，对照书本代码，发现问题：
//书中给的样例全是强连通图，但测试点中有非强连通图。 修改提交AC.2017-9-30
#include <stdio.h>
#include <string.h>
int a[110][110];
int d[110],f[110],vis[110],tag=0,n;//第一次访问d[] 最后一次访问f[]
void dfs(int u){
int v;
vis[u]=1;
tag++;
d[u]=tag;
for(v=1;v<=n;v++)
if(vis[v]==0&&a[u][v])
dfs(v);
tag++;
f[u]=tag;
}
int main(){
int i,j,u,k,v;
memset(a,0,sizeof(a));
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d%d",&u,&k);
for(j=1;j<=k;j++){
scanf("%d",&v);
a[u][v]=1;
}
}
for(i=1;i<=n;i++)//1漏了该功能，导致WA //书中给的样例全是强连通图，但测试点中有非强连通图。
if(vis[i]==0)
dfs(i);
for(i=1;i<=n;i++)
printf("%d %d %d\n",i,d[i],f[i]);
return 0;
}
根据上述方法二的思想，采用栈，根据自己的理解，写了如下AC代码：
//ALDS1_11_B:Depth First Search
//体会，算法清晰，便思如泉涌2017-10-1 9:38 AC方法二
//C(用栈实现的深度优先搜索)
#include <stdio.h>
#include <string.h>
int n,a[110][110],vis[110],d[110],f[110],tag=0;
void dfs(int x){
int u,v,stack[110],top=0;//stack栈从数组元素1开始使用
top++;//top指向栈顶元素
stack[top]=x;
vis[x]=1;//1 此处写成 vis[top]=1; 低级错误
tag++;
d[x]=tag;
while(top){
u=stack[top];
for(v=1;v<=n;v++)
if(vis[v]==0){
if(a[u][v]){
top++;
stack[top]=v;
vis[v]=1;
tag++;
d[v]=tag;
break;
}
}
if(v==n+1){//没有连线可到的点可用
tag++;
f[u]=tag;
top--;
}
}
}
int main(){
int u,k,v,i,j;
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d%d",&u,&k);
for(j=1;j<=k;j++){
scanf("%d",&v);
a[u][v]=1;
}
}
for(i=1;i<=n;i++)
if(vis[i]==0)
dfs(i);
for(i=1;i<=n;i++)
printf("%d %d %d\n",i,d[i],f[i]);
return 0;
}
12.4 广度优先搜索
ALDS1_11_C:Breadth First Search
原书AC代码：2017-10-1 21:30抄写完成
//ALDS1_11_C:Breadth First Search
#include <iostream>
#include <queue>
using namespace std;
static const int N=100;
static const int INFTY=(1<<21);
int n,M[N][N];
int d[N];//通过距离管理访问状态(color)
void bfs(int s){
queue<int> q;//使用标准库中的queue
q.push(s);
for(int i=0;i<n;i++)d[i]=INFTY;
d[s]=0;
int u;
while(!q.empty()){
u=q.front();q.pop();
for(int v=0;v<n;v++){
if(M[u][v]==0)continue;
if(d[v]!=INFTY)continue;
d[v]=d[u]+1;
q.push(v);
}
}
for(int i=0;i<n;i++){
cout<<i+1<<" "<<((d[i]==INFTY)?(-1):d[i])<<endl;
}
}
int main(){
int u,k,v;
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)M[i][j]=0;
}
for(int i=0;i<n;i++){
cin>>u>>k;
u--;
for(int j=0;j<k;j++){
cin>>v;
v--;
M[u][v]=1;
}
}
bfs(0);
return 0;
}
这次没有仿照上述代码，本人未看书，直接编写的C语言AC代码如下：
为了方便大家，提供一组样例：
输入：
5
1 2 2 4
2 1 4
3 0
4 1 3
5 0
输出：
1 0
2 1
3 2
4 1
5 -1
//ALDS1_11_C:Breadth First Search
//迪杰斯特拉算法肯定能解决该题，但有《啊哈！算法》的基础，广搜也肯定能解决该题，先自己动手
//样例通过，提交WA，重读题目，发现If there are no path from vertex 11 to vertex uu, print -1 as the shortest distance.
//即无路可达，需要输出-1，马上修改,提交WA ,4 此处写成 for(j=1;j<=n;j++) 大失水准，该句，查了10分钟。
//继续修改，提交WA ,马上对应输入输出，发现测试语句未删除，果断删除，提交AC 2017-10-1 10:59
//通过该题，发现对迪杰斯特拉算法以及广度优先遍历的理解又上了一个台阶。
#include <stdio.h>
#include <string.h>
struct node{
int v,s;//v点，到起点的步数
}q[110];
int n,a[110][110],vis[110],head,tail,step[110];//step[]记录各点步数
void breadth(){
int u,v;
head=tail=1;
vis[1]=1;//3 漏了该句
q[head].v=1;
q[head].s=0;
step[1]=0;
tail++;
while(head<tail){
u=q[head].v;
for(v=1;v<=n;v++)
if(vis[v]==0&&a[u][v]){
vis[v]=1;//2 漏了该句
q[tail].v=v;
q[tail].s=q[head].s+1;//1 该句写成 q[tail].s+=1;
step[v]=q[tail].s;
tail++;
}
head++;
}
}
int main(){
int u,k,v,i,j;
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));
memset(step,-1,sizeof(step));//3此处写成 memset(step,0,sizeof(step)); 即无路可达，需要输出-1，
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d%d",&u,&k);
for(j=1;j<=k;j++){//4 此处写成 for(j=1;j<=n;j++) 大失水准，该句，查了10分钟。
scanf("%d",&v);
a[u][v]=1;
}
}
breadth();
for(i=1;i<=n;i++)
printf("%d %d\n",i,step[i]);
return 0;
}
12.5 连通分量
ALDS1_11_D:Connected Components
很不幸，在在线测评网站搜索该题，已无踪影，看来只有样例好用了，无法知道程序是否AC,重新进行寻找，发现在线测评网站，该题还在，眼花了啊。
原书AC代码：
//ALDS1_11_D:Connected Components
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
static const int MAX=100000;
static const int NIL=-1;
int n;
vector<int> G[MAX];
int color[MAX];
void dfs(int r,int c){
stack<int> S;
S.push(r);
color[r]=c;
while(!S.empty()){
int u=S.top();S.pop();
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(color[v]==NIL){
color[v]=c;
S.push(v);
}
}
}
}
void assignColor(){
int id=1;
for(int i=0;i<n;i++)color[i]=NIL;
for(int u=0;u<n;u++){
if(color[u]==NIL)dfs(u,id++);
}
}
int main(){
int s,t,m,q;
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>s>>t;
G[s].push_back(t);
G[t].push_back(s);
}
assignColor();
cin>>q;
for(int i=0;i<q;i++){
cin>>s>>t;
if(color[s]==color[t]){
cout<<"yes"<<endl;
}else{
cout<<"no"<<endl;
}
}
return 0;
}
仿照上述代码，本人编写的C语言AC代码如下：
方法一：广度优先遍历
//ALDS1_11_D:Connected Components
//仔细想了想该题，对同一联通区块的节点，染上相同的颜色，不同区块，染色不同，采用广度优先遍历来实现。
//染色后，对于每次查找，都可以保证O(1)的算法时间复杂度
//请注意，朋友之间的关系，属无向图，为此还偷瞄了书中代码。2017-10-2 10:58 书中样例通过，遗憾该题已被在线测评网站移除。
//重新进行寻找，发现在线测评网站，该题还在，眼花了啊。
//提交Presentation Error, 少一个回车都不行啊。修改，printf("no\n");//1 printf("no");提交Presentation Error;提交 Wrong Answer
//重新读题，发现The users in the SNS are identified by IDs 0,1,...,n-1. 本人误以为是1-n,马上修改 for(i=0;i<=n-1;i++)//2 for(i=1;i<=n;i++)
//提交Wrong Answer, 怎么查都没问题，突然想到，无向图，边数应为关系的两倍， e[100100*2];//3 e[100100] 无向图，故边数应为2*m
//修改，提交AC. 2017-10-2 11:18 调试错误，整整用了20分钟。一看，还都是以往遇到的问题。
#include <stdio.h>
#include <string.h>
struct node{
int to,next;
}e[100100*2];//3 e[100100] 无向图，故边数应为2*m
int cnt=0,head[100100],n,m,q[100100],vis[100100],color[100100];
void add(int u,int v){
cnt++,e[cnt].to=v,e[cnt].next=head[u],head[u]=cnt;
}
void bfs(int x,int c){//广度优先遍历，染色
int h,t,u,v,b;//b边
h=t=1;
vis[x]=1;
q[t]=x;
color[x]=c;
t++;
while(h<t){
u=q[h];
for(b=head[u];b;b=e[b].next){
v=e[b].to;
if(vis[v]==0){
vis[v]=1;
q[t]=v;
color[v]=c;
t++;
}
}
h++;
}
}
int main(){
int i,u,v,c=0,k;
memset(head,0,sizeof(head));
memset(vis,0,sizeof(vis));
memset(color,0,sizeof(color));
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&u,&v);
add(u,v);//无向图
add(v,u);
}
for(i=0;i<=n-1;i++)//2 for(i=1;i<=n;i++)
if(vis[i]==0)
bfs(i,++c);
scanf("%d",&k);
for(i=1;i<=k;i++){
scanf("%d%d",&u,&v);
if(color[u]==color[v])
printf("yes\n");
else
printf("no\n");//1 printf("no");提交Presentation Error
}
return 0;
}
方法二：深度优先遍历
//ALDS1_11_D:Connected Components
//突发奇想，用该题练练一题多解。
//方法：深度优先遍历
#include <stdio.h>
#include <string.h>
struct node{
int to,next;
}e[100100*2];
int cnt=0,head[100100],n,m,q[100100],vis[100100],color[100100];
void add(int u,int v){
cnt++,e[cnt].to=v,e[cnt].next=head[u],head[u]=cnt;
}
void dfs(int x,int c){//深度优先遍历，染色
int v,b;//b边
vis[x]=1;
color[x]=c;
for(b=head[x];b;b=e[b].next){//1此处写成 for(b=head[u];b;b=e[b].next)
v=e[b].to;
if(vis[v]==0)
dfs(v,c);
}
}
int main(){
int i,u,v,c=0,k;
memset(head,0,sizeof(head));
memset(vis,0,sizeof(vis));
memset(color,0,sizeof(color));
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&u,&v);
add(u,v);//无向图
add(v,u);
}
for(i=0;i<=n-1;i++)
if(vis[i]==0)
dfs(i,++c);
scanf("%d",&k);
for(i=1;i<=k;i++){
scanf("%d%d",&u,&v);
if(color[u]==color[v])
printf("yes\n");
else
printf("no\n");
}
return 0;
}
方法三：并查集，Wrong Answer算法
//ALDS1_11_D:Connected Components
//方法：并查集
//样例很快通过，提交Wrong Answer ,经检验，感觉是算法复杂度过大，引起的错误，故还是留在该篇文章中，待日后水平更高后，来解决。2017-10-2 17:05
#include <stdio.h>
int n,m,f[100100];
int getf(int u){
if(f[u]==u)
return u;
f[u]=getf(f[u]);
return f[u];
}
void merge(int u,int v){//靠左
int f1=getf(u),f2=getf(v);
if(f1!=f2)
f[f2]=f1;
}
int main(){
int i,j,u,v,k;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
f[i]=i;
for(i=1;i<=m;i++){
scanf("%d%d",&u,&v);
merge(u,v);
}
scanf("%d",&k);
for(i=1;i<=k;i++){
scanf("%d%d",&u,&v);
if(f[u]==f[v])
printf("yes\n");
else
printf("no\n");
}
return 0;
}
2017-10-2 11:18AC该章节内容。