社区讨论
死循环求助
B3644【模板】拓扑排序 / 家谱树参与者 2已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lycza0rq
- 此快照首次捕获于
- 2024/07/08 20:48 2 年前
- 此快照最后确认于
- 2024/07/08 22:55 2 年前
代码:
CPP#include<bits/stdc++.h>
using namespace std;
class Graph
{
public:
int V;//顶点数
vector<list <int > >adj;//邻接表
//构造函数,初始化图的顶点数和邻接表
Graph(int V)
{
this->V=V;
adj.resize(V);//根据顶点数调整邻接表的大小
}
//添加边的方法,无向图需要在两个顶点的邻接表中都添加对方
void addEdge(int v,int w)
{
adj[v].push_back(w);//在顶点v的邻接表中添加顶点w
}
//删除节点的方法,同时删除与该节点相关的所有边
void removeNode(int v)
{
if(v<0||v>=V)
{//检查节点索引是否有效
cout<<"Invalid node index"<<endl;//输出错误信息
return;//返回,不执行后续操作
}
cout<<v<<" ";
//遍历所有顶点,删除与顶点v相关的边
for(int i=0;i<V;i++)
adj[i].remove(v);//从每个顶点的邻接表中删除顶点v
//删除顶点v本身的所有边
adj[v].clear();//清空顶点v的邻接表
}
int findInDegree(int x)
{
int result=100;//存储结果
for(int i=0;i<V;i++)
if(adj[i].size()==x)result=i;//如果节点i的入度等于x,将节点i添加到结果中
return result;//返回结果
}
bool isEmpty()
{
for(int i=0;i<V;i++)
{
if(!adj[i].empty())//如果存在非空的邻接表
return false;//图不为空
}
return true;//所有邻接表都为空,图为空
}
};
int main()
{
int n;
cin>>n;
Graph g(n);
for(int i=0;i<=n-1;i++)
{
int tmp;
do
{
cin>>tmp;
if(tmp!=0)g.addEdge(i,tmp);
}while(tmp!=0);
}
while(!g.isEmpty())
g.removeNode(g.findInDegree(0));
return 0;
// Graph g(3);
// g.addEdge(0,1);
// g.addEdge(1,2);
// g.removeNode(2);
// cout<<g.findInDegree(0)+1;
}
输入:
CPP5
0
4 5 1 0
1 0
5 3 0
3 0
输出:
CPP0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0......
回复
共 4 条回复,欢迎继续交流。
正在加载回复...