Trova la Trasposta di un Grafo
Dato un grafo orientato con
v vertici e e archi, ti viene richiesto di trovarne la trasposta.La trasposta di un grafo orientato è un grafo ottenuto invertendo la direzione di tutti i suoi archi. In altre parole, è un grafo in cui tutti gli archi orientati del grafo originale vengono invertiti.
La trasposta di un grafo è utile per trovare percorsi inversi o relazioni inverse nel grafo. Vedremo alcune applicazioni più avanti nel corso.
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), il che significa che il vertice v1 è collegato al vertice v2.Output
Il programma deve stampare la lista di adiacenza del grafo complementare. Ogni riga dovrebbe iniziare con l’id di un vertice, seguito da un punto e virgola (
:) e poi le sue connessioni. Le connessioni in ciascuna riga vanno separate da uno spazio. L’ordine sia dei vertici sia delle connessioni può essere arbitrario.Esempi
Ingresso | Uscita |
4 4
1 2
1 4
2 4
3 4 | 1:
2: 1
3:
4: 1 2 3 |
Constraints
Time limit: 3.5 seconds
Memory limit: 512 MB
Output limit: 1 MB