1 条题解

  • 0
    @ 2025-2-14 21:30:05

    C++ :

    #include<cstdio>
    #include<vector>
    #include<queue>
    using namespace std;
    
    int n,m;
    
    struct node
    {
    	vector<int> adj[100];
    	int indeg[100];
    }p;
    
    void add(node &N,int u,int v)
    {
    	N.adj[u].push_back(v);
    	N.indeg[v]++;
    }
    
    int toposort(node N)
    {
    	int count=0,i;
    	queue<int> q;
    	for(i=0;i<n;i++)
    	{
    		if(!N.indeg[i])
    			q.push(i);
    	}
    	while(!q.empty())
    	{
    		count++;
    		int x=q.front();
    		q.pop();
    		for(vector<int>::iterator it=N.adj[x].begin();it!=N.adj[x].end();it++)
    			if(!(--N.indeg[*it]))
    				q.push(*it);
    	}
    	if(count==n)
    		return 1;
    	else
    		return 0;
    }
    
    int main()
    {
    	int i,u,v;
    	while(scanf("%d%d",&n,&m)!=EOF,n)
    	{
    		for(i=0;i<n;i++)
    		{
    			p.adj[i].clear();
    			p.indeg[i]=0;
    		}
    		while(m--)
    		{
    			scanf("%d%d",&u,&v);
    			add(p,u,v);
    		}
    		if(toposort(p))
    			puts("YES");
    		else
    			puts("NO");
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    933
    时间
    1000ms
    内存
    32MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者