百撕不得骑姐
  • 板块P1347 排序
  • 楼主fufuQAQ
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/4/16 17:13
  • 上次更新2023/10/28 03:35:06
查看原帖
百撕不得骑姐
668320
fufuQAQ楼主2022/4/16 17:13
cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,c[610];
bool flag;
int tmp;

struct ty{
    int t;//t存放这条边和哪条边连接 
	int next; //next存放下一个点的下标是谁           
}edge[100010];

int head[1010];//记录下一个节点指向的下标 
int cnt=0;

void addedge(int x,int y)//链式前向星 存储图 
{
	edge[++cnt].t = y;
	edge[cnt].next = head[x];
	head[x] = cnt;
}

int inc[1010]; //存放这条边有几个元素入度
queue<int> q; 

int tuopu()//拓扑排序 
{
	bool flag2=0;
	if(flag==0)
	{
	    for(int i=1;i<=n;i++)//访问所有的点 
	    {
		    if(inc[i] == 0)//是一个可以直接拿出来的点
		    {
		       flag2=1;
		       q.push(i); 
		    }
    	}
    }
    else if(flag==1)
    {
    	for(int i=1;i<=tmp;i++)//访问所有的点 
	    {
		    if(inc[i] == 0)//是一个可以直接拿出来的点
		    {
               flag2=1;
		       q.push(i); 
		    }  
    	}
	}
	if(flag2==0)  return 0;//讨论矛盾的情况 
	int tot=0;//记录已经输出的点的个数 
	while(!q.empty())
	{
		int x=q.front();
		cout<<x<<' '<<endl; 
		q.pop();
		tot++;
		for(int i=head[x]; i!=-1; i=edge[i].next)//访问与x相邻的所有的边
		{
		 	inc[edge[i].t]--;
		 	if(inc[edge[i].t] == 0) 
		 	   q.push(edge[i].t);
		}
	}
	cout<<"tot="<<tot<<endl;
	if(flag==1)//所给的条件满足关系 
	{
	    if(tot != tmp)  return 0;
	    else return 1;//能成功找到 
	}
	else 
	{
		if(tot != n)  return 0;
	    else return 1;//能成功找到 
	}
}

int main()
{
	cin>>n>>m;
	string s="";
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++)
	{
		flag=0;
		char x,y;
		char t;
		cin>>x>>t>>y;
		int a=x-'0';   int b=y-'0';
//		c[a]=1;   c[b]=1;
		if(c[a]==0)  s+=x;
		if(c[b]==0)  s+=y;
		c[a]=1;   c[b]=1;
		
		if(t=='>')
		{
			addedge(a,b);
			inc[b]++;
		}
		else
		{
			addedge(b,a);
		    inc[a]++;
		}
		
	    tmp=s.size();
//	    cout<<"tmp="<<tmp<<" ";
		if(tmp<n)  flag=1;
//		cout<<i<<" "<<flag<<endl;
		if(flag==0 && tuopu()==1)//能成功找到
	    {
		    sort(s.begin(),s.end());
		    cout<<"Sorted sequence determined after "<<i<<" relations: "<<s<<"."<<endl;
		    return 0;
	    }  
	    else if(tuopu()==0 && i!=m )//&& flag)//第二种情况 
	    {
	    	cout<<"Inconsistency found after "<<i<<" relations." <<endl;
//	    	return 0;
		}
		else if(tuopu()==0 && i==m)
		{
		    cout<<"Sorted sequence cannot be determined."<<endl;
		    return 0;
		}
	}
  
	return 0;
}
2022/4/16 17:13
加载中...