1.邻接矩阵存无向连通图，用DFS求所有割顶，按顶点序号升序输出。
递归实现：
#include <bits/stdc++.h>
using namespace std;
bool AdjMat[100][100];
int n;
int res[100];
int num;
void CreatGraph(){
cin>>n;
int u,v;
while(cin>>u>>v){
AdjMat[u][v]=1;
AdjMat[v][u]=1;
}
}
int cnt,vis[100],low[100];
void dfs(int v){
vis[v]=++cnt;
int minn=vis[v];
for(int w=0;w<n;w++){
if(AdjMat[v][w]){
if(!vis[w]){
dfs(w);
minn=min(minn,low[w]);
if(low[w]>=vis[v]) res[num++]=v;
}
else if(vis[w]<minn) minn=vis[w];
}
}
low[v]=minn;
}
void FindArt(){
cnt=vis[0]=1;
int v=0;
while(v<n){
if(AdjMat[0][v]){
dfs(v);break;
}
v++;
}
if(cnt<n){
res[num++]=0;
while(v<n){
if(AdjMat[0][v]&&!vis[v]) dfs(v);
v++;
}
}
}
void output(){
sort(res,res+num);
for(int i=0;i<num;i++) cout<<res[i]<<' ';
}
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
CreatGraph();
FindArt();
output();
return 0;
}
非递归实现：
#include <bits/stdc++.h>
using namespace std;
bool AdjMat[100][100];
int n;
int res[100];
int num;
void CreatGraph(){
cin>>n;
int u,v;
while(cin>>u>>v){
AdjMat[u][v]=1;
AdjMat[v][u]=1;
}
}
int cnt,vis[100],low[100],pre[100];
//pre保存dfs生成树中每个顶点的父结点
stack<int> s;
void output(){
sort(res,res+num);
for(int i=0;i<num;i++) cout<<res[i]<<' ';
}
void dfs(int v){
while(!s.empty()) s.pop();
s.push(v);
while(!s.empty()){
v=s.top();
if(!vis[v]){
vis[v]=++cnt;
low[v]=vis[v];
}
bool flag=0;
for(int w=0;w<n;w++){
if(AdjMat[v][w]){
if(!vis[w]){
pre[w]=v;
s.push(w);
flag=1;
break;
}
else if(pre[w]==v) low[v]=min(low[v],low[w]);
else if(vis[w]<vis[v]) low[v]=min(low[v],vis[w]);
}
}
if(!flag){
for(int w=0;w<n;w++){
if(AdjMat[v][w]&&pre[w]==v&&low[w]>=vis[v]){
res[num++]=v;
break;
}
}
s.pop();
}
}
}
void FindArt(){
cnt=vis[0]=1;
int v=0;
while(v<n){
if(AdjMat[0][v]){
dfs(v);break;
}
v++;
}
if(cnt<n){
res[num++]=0;
while(v<n){
if(AdjMat[0][v]&&!vis[v]) dfs(v);
v++;
}
}
}
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
CreatGraph();
FindArt();
output();
return 0;
}
2.邻接表存无向连通图，BFS求0到其他顶点的最短路径长和最短路。
#include <bits/stdc++.h>
using namespace std;
struct ArcNode{
int to;
ArcNode* next;
};
struct VNode{
int id;
int pre;
int depth;
ArcNode* first;
}vex[100];
void AddEdge(int u,int v){
if(!vex[u].first){
vex[u].first=new ArcNode;
vex[u].first->to=v;
vex[u].first->next=NULL;
return;
}
ArcNode* p=new ArcNode;
p->next=vex[u].first;
p->to=v;
vex[u].first=p;
}
int n;
void CreatGraph(){
int u,v;
cin>>n;
for(int i=0;i<n;i++) vex[i].id=i;
while(cin>>u>>v){
AddEdge(u,v);
AddEdge(v,u);
}
}
queue<int> q;
void bfs(){
q.push(0);
while(!q.empty()){
int u=q.front();q.pop();
ArcNode *p=vex[u].first;
while(p){
if(!vex[p->to].depth){
q.push(vex[p->to].id);
vex[p->to].depth=vex[u].depth+1;
vex[p->to].pre=u;
}
p=p->next;
}
}
}
void output(int v){
if(!v) cout<<0;
else{
output(vex[v].pre);
cout<<"->"<<v;
}
}
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
CreatGraph();
bfs();
for(int i=1;i<n;i++){
cout<<vex[i].depth<<' ';
output(i);
cout<<'\n';
}
return 0;
}
3.邻接矩阵存带权无向图，判断是否有圈；若有，输出权最大的圈和它的权。
#include <bits/stdc++.h>
using namespace std;
int AdjMat[100][100];
int n;
void CreatGraph(){
cin>>n;
int u,v,w;
while(cin>>u>>v>>w){
AdjMat[u][v]=w;
AdjMat[v][u]=w;
}
}
vector<int> res,temp;
int sum,tsum;
bool vis[100][100];
void output(int sum,vector<int> res){
cout<<sum<<endl;
int len=res.size();
for(int i=0;i<len-1;i++) cout<<res[i]<<"->";
cout<<res[len-1]<<endl;
}
void dfs(int u,int v){
for(int i=0;i<n;i++){
if(AdjMat[u][i]&&!vis[u][i]){
if(i==v){
if(tsum+AdjMat[u][v]>sum){
sum=tsum+AdjMat[u][v];
res=temp;
res.push_back(v);
}
}
else{
vis[u][i]=vis[i][u]=1;
temp.push_back(i);
tsum+=AdjMat[u][i];
dfs(i,v);
tsum-=AdjMat[u][i];
temp.pop_back();
vis[u][i]=vis[i][u]=0;
}
}
}
}
void solve(){
for(int u=0;u<n;u++){
temp.clear();
temp.push_back(u);
dfs(u,u);
for(int v=0;v<n;v++) if(AdjMat[u][v]) vis[u][v]=1;
}
if(!sum) cout<<"No circle!"<<endl;
else output(sum,res);
}
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
CreatGraph();
solve();
return 0;
}
