0分不知道为什么不过,求调谢谢
查看原帖
0分不知道为什么不过,求调谢谢
737014
Xuwindows_WS楼主2024/7/26 15:29
#include<bits/stdc++.h>
using namespace std;
int n;//节点个数
bool vis[100010];//数组指针和答案数组
int in[100010];//入度
vector<int>gp[100010];
void toposort()//拓扑排序的函数
{
	queue<int>q;//入读为0的队列
	for(int i=1;i<=n;i++)
	{
		if(in[i]==1)q.push(i),vis[i]=true;
	}//将入度为0的节点加入队列
	while(!q.empty())
	{
		int f=q.front();//取队头结点
		q.pop();//别忘了把队头出队
		for (int i=1;i<=gp[f].size();i++)//遍历与队头相邻的节点
		{
			int k=gp[f][i];
			in[k]--;//入度-1
			if(in[k]==1)q.push(k),vis[k]=true;//入度为0就入队
		}
	}
}
int main()
{
	memset(vis,0,sizeof(vis));
    //读入
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x,y;
        cin>>x>>y;
        gp[x].push_back(y);
        gp[y].push_back(x);
        in[x]++;
        in[y]++;
	}
	toposort();//调用拓扑排序的函数
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])cout<<i<<' ';
    }
	return 0;
}
2024/7/26 15:29
加载中...