社区讨论

死循环求助

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;
}
输入:
CPP
5
0
4 5 1 0
1 0
5 3 0
3 0
输出:
CPP
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 0......

回复

4 条回复,欢迎继续交流。

正在加载回复...