Verificare se il Grafo è Bipartito
Un grafo si definisce bipartito quando è possibile colorarlo con due colori in modo che nessun paio di vertici adiacenti condivida lo stesso colore.
Stabilire se un grafo è bipartito può aiutare a identificare strutture e proprietà particolari, consentendo di risolvere in modo efficiente problemi in ambiti come la pianificazione, l’allocazione delle risorse e la risoluzione di conflitti. Inoltre, i grafi bipartiti permettono di sfruttare algoritmi più semplici e ottimizzazioni in attività come il matching massimo (maximum matching) e la colorazione dei grafi (graph coloring).
Vi viene fornito un grafo non orientato con
v vertici e e spigoli. È richiesto di verificare se il grafo è bipartito oppure no.Input
La prima riga dell’input contiene due interi
v (1 ≤ v ≤ 100 000) ed e (1 ≤ e ≤ 100 000).Le successive
e righe contengono coppie di interi v1, v2 (1 ≤ v1, v2 ≤ v). Ciò significa che il vertice v1 è connesso al vertice v2 e viceversa.Output
Il programma deve stampare
Yes se il grafo in questione è bipartito, altrimenti deve stampare No.Esempi
Input | Output |
2 1
2 1 | Yes |
3 2
2 1
1 3 | Yes |
3 3
1 2
1 3
2 3 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB