Envío 3894

Problema 0x53 - Encontrar ciclos en un grafo dirigido

Autor: Jhon_z09
Fecha: 2021-04-20 20:45:50 UTC (Hace más de 3 años)

Caso #	Resultado	Tiempo	Memoria
#1	Correcto	0.006 s	2 KBi
#2	Correcto	0.004 s	2 KBi
#3	Correcto	0.007 s	2 KBi
#4	Incorrecto	0.006 s	2 KBi
#5	Correcto	0.004 s	7 KBi
#6	Correcto	0.002 s	2 KBi
#7	Correcto	0.008 s	1 KBi
#8	Correcto	0.01 s	1 KBi
#9	Correcto	0.006 s	1 KBi
#10	Correcto	0.006 s	1 KBi
#11	Correcto	0.003 s	2 KBi
#12	Correcto	0.008 s	1 KBi
#13	Correcto	0.003 s	2 KBi
#14	Correcto	0.003 s	2 KBi
#15	Incorrecto	0.004 s	2 KBi
#16	Correcto	0.004 s	2 KBi
#17	Correcto	0.007 s	3 KBi
#18	Correcto	0.003 s	2 KBi
#19	Correcto	0.004 s	2 KBi
#20	Correcto	0.006 s	2 KBi
#21	Incorrecto	0.006 s	1 KBi
#22	Correcto	0.006 s	5 KBi
#23	Correcto	0.002 s	2 KBi
#24	Correcto	0.005 s	4 KBi
#25	Correcto	0.008 s	2 KBi
#26	Correcto	0.006 s	2 KBi
#27	Incorrecto	0.048 s	2 KBi
#28	Correcto	0.01 s	1 KBi
#29	Correcto	0.064 s	3 KBi
#30	Correcto	0.003 s	2 KBi
#31	Incorrecto	0.01 s	2 KBi
#32	Correcto	0.044 s	3 KBi
#33	Correcto	0.017 s	2 KBi
#34	Incorrecto	0.016 s	2 KBi
#35	Correcto	0.059 s	2 KBi

Puntos totales: 83 / 100

Código

#include <bits/stdc++.h>
using namespace std;
#define PB push_back

int main(){
    int n, m; cin >> n >> m;
    vector<vector<int>> graph(n);
   
    for(int i = 0 ; i < m; ++i){
    	int u, v; cin >> u >> v;
    	graph[u].PB(v);
	}
   

	queue<int> q;
    vector<bool> used(n);
    vector<int> d(n);
    bool f  = true;
    for(int start = 0; start < n and f; ++start){
    	if(used[start]) continue;
    	
    	q.push(start);
    	used[start] = true;
	    d[start] = 0;
		while(!q.empty() and f){
	    	int curr = q.front();
	    	q.pop();

	    	for(int adj: graph[curr]){
	    		if(used[adj] and d[adj] < d[curr]){ 
					f = false; break;
				}
				else if(used[adj]) continue;
				else{
		    		used[adj] = true;
		    		q.push(adj);
		    		d[adj] = d[curr] + 1;
	    		}
			}
		}
	}
    
    if (f) cout << "No";
    else cout << "Yes";
	
	return 0;
}