1 solutions

  • 0
    @ 2025-11-5 20:17:11

    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

    Information

    ID
    20224
    Time
    1000ms
    Memory
    32MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By